A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis
Authors: Damien Ferbach
Christos Tsirigotis
Gauthier Gidel
Joey Bose
Venue: ICLR 2023 poster (2023)
Keywords: Equivariant Networks
Strong Lottery Ticket
Weight Pruning

Abstract: The Strong Lottery Ticket Hypothesis (SLTH) stipulates the existence of a subnetwork within a sufficiently overparameterized (dense) neural network that---when initialized randomly and without any training---achieves the accuracy of a fully trained target network. Recent works by Da Cunha et. al 2022, Burkholz 2022 demonstrate that the SLTH can be extended to translation equivariant networks---i.e. CNNs---with the same level of overparametrization as needed for the SLTs in dense networks. However, modern neural networks are capable of incorporating more than just translation symmetry, and developing general equivariant architectures such as rotation and permutation has been a powerful design principle. In this paper, we generalize the SLTH to functions that preserve the action of the group $G$---i.e. $G$-equivariant network---and prove, with high probability, that one can approximate any $G$-equivariant network of fixed width and depth by pruning a randomly initialized overparametrized $G$-equivariant network to a $G$-equivariant subnetwork. We further prove that our prescribed overparametrization scheme is optimal and provide a lower bound on the number of effective parameters as a function of the error tolerance. We develop our theory for a large range of groups, including subgroups of the Euclidean $\text{E}(2)$ and Symmetric group $G \leq \mathcal{S}_n$---allowing us to find SLTs for MLPs, CNNs, $\text{E}(2)$-steerable CNNs, and permutation equivariant networks as specific instantiations of our unified framework. Empirically, we verify our theory by pruning overparametrized $\text{E}(2)$-steerable CNNs, $k$-order GNNs, and message passing GNNs to match the performance of trained target networks.

Published as a conference paper at ICLR 2023
A GENERAL FRAMEWORK FOR PROVING THE EQUIV- ARIANT STRONG LOTTERY TICKET HYPOTHESIS
Damien Ferbach"
Christos Tsirigotis Université de Montréal and Mila
École Normale Supérieure, PSL, and Mila damien. ferbach@ens psp
Gauthier Gidel
Avishek (Joey) Bose
Université de Montréal and Mila
McGill University and Mila
ABSTRACT
The Strong Lottery Ticket Hypothesis (SLTH) stipulates the existence of subnet- work within a sufficiently overparameterized (dense) neural network that-when initialized randomly and without any vrining-achiess trained target network. Recent works by da Cunha et al. (2022b); Burkholz (2022a) demonstrate that the SLTH be extended translation equivariant networks-i.e. CNNs-with the same level of overparametrization as needed for the SL.Ts in dense networks. However, modern neural networks are capable of incorporating than just translation symmetry, and developing general equivariant architectures such as rotation and permutation has been a powerful design principle. In this paper, we generalize the SLTH to functions that preserve the action of the group G-i.e. G-equivariant network-and prove, with high probability, that one can approxi- mate any G-equivariant network of fixed width and depth by pruning a randomly initialized overparametrized G-equivariant network a G-equivariant subnetwork. We further prove that our prescribed overparametrization scheme is optimal and function of
the accuracy of fully
provides a lower bound on the number of effective parameters the error tolerance. We develop our theory for large range of groups, including subgroups of the Euclidean E(2) and Symmetric group G S S, allowing us find SLTs for MLPs, CNNs, E(2)-stecrable CNNs, and permutation equivariant networks specific instantiations of our unified framework. Empirically, we verify our theory by pruning overparametrized E(2)-steerable CNNs, k-order GNNs, and message passing GNNs match the performance of trained target networks.
INTRODUCTION
Many problems in deep learning benefit from massive amounts of annotated data and compute that enables the training of models with excess of billion parameters. Despite this appeal of over- parametrization many world applications are resource- resource-constrainee constrained (c.g., on device) and demand a reduced computational footprint for both training and deployment (Deng et al., 2020), A natural ques- tion that arises in these settings is then: it possible to marry the benefits of large models eeniirially beneficial for effective training the computational efficiencies of smaller sparse models?
standard line of work for building compressed models from larger fully trained networks with minimal loss in accuracy is via weight pruning (Blalock et al., 2020). There is, however, increasing empirical evidence to suggest weight pruning can occur significantly prior to full model convergence. Frankle and Carbin (2019) postulate the extreme scenario termed lottery ticket hypothesis (LTH) where subnetwork extracted at initialization can be trained to the accuracy of the parent network in striking phenomenon Ramanujan
effect "winning" the weight initialization lottery. In an et al. (2020) find that not only do such sparse subnetworks exist at initialization but they already achieve impressive performance without any training. This remarkable occurrence termed the
"denotes equal contribution.
Work done during an internship at Mila
1 Canada Cifar AT Chair

---

Published as a conference paper at ICLR 2023
strong lottery ticket hypothesis (SLTH) was proven for overparametrized dense networks with no biases (Malach et al., 2020; Pensia et al., 2020; Orseau et al., 2020), non-zero biases (Fischer and Burkholz, 2021), and vamilla CNNs (da Cunha et al., 2022b). Recently, Burkholz (2022b) extended the work of Pensia et al. (2020) to most activation functions that behave like ReLU around the origin, and adopted another overparamettization framework in Pensia et al. (2020) such that the overparametrized network has depth L + 1 (no longer 2L). However, the optimality with respect to the number of parameters (Theorem 2 in Pensia et al. (2020)) is lost with this method. Moreover, Burkholz (2022a) extended the results of da Cunha et al. (2022b) on CNNS to non-positive inputs.
Modern architectures, however, are more than just MLPs and CNNs and many encode data data-dependent inductive biases in the form of equivariances and invariances that are pivotal to learning smaller and simultancously
more efficient networks (He et al., 2021). This raises the important question: get the benefits of equivariance and pruning? In other words, does there exist winning tickets for the equivariant strong lottery for general equivariant networks given sufficient overparametrization?
Present Work. In this paper, we develop a unifying framework to study and prove the existence of strong lottery tickets (SLTs) for general equivariant networks. Specifically, in our main result (Thm. 1) we prove that any fixed width and depth target G-equivariant network that uses a point-wise ReLU can be approximated with high probability to pre-specified tolerance by subnetwork within a random G-equivariant network that is overparametrized by doubling the depth and increasing the width by a logarithmic factor: Such theorem allows us to immediately recover the results of Pensia et al. (2020); Orseau et al. (2020) for MLPs and of Burkholz et al. (2022); da Cunha et al. (2022b) for CNNs as spe- cific instantiations under our unified equivariant framework. Furthermore, we prove that logarithmic overparametrization is necessarily optimal- by providing a lower bound in Thm. 2-as as a function of the tolerance. Crucially, this is irrespective of which overparamettization strategy is employed which demonstrates the optimality of Theorem 1. Notably, the extracted subnetwork is also G-equivariant, preserving the desirable inductive biases of the target model; such a fact is importantly not achievable via a simple application of previous results found in (Pensia et al., 2020; da Cunha et al., 2022b).
Our theory is broadly applicable to any equivariant network that uses a pointwise ReLU nonlinearity. This includes the popular Etee-steerable CNNs with regular representations (Weiler and Cesa, 2019) (Corollary 1) that model symmetries of the 2d-plane as well as subgroups of the symmetric group of n elements Sn,, allowing us to find SL.Ts for permutation equivariant networks (Corollary 2) as a specific instantiation. We substantiate our theory by conducting experiments by explicitly computing the pruming masks for randomly initialized overparametrized B(2)- networks, k-order GNNs, and MPGNNs to approximate another fully trained target equivariant network.
2 BACKGROUND AND RELATED WORK
Notation and Convention. For E E N. [p] denotes {0...., .p. 1}. We assume that the starting index of tensors (vectors, matrices....) is O, e.g., W Wpg. P [d]. G is a group, and p is its representation. We use |- for the cardinality of set, while O represents the direct sum of vector spaces or group representations and @ indicates the Kroenecker product. We use * to denote a convolution. We define x² _ as x max(0, .)) and x= min (0, .r. - is Ep norm while ||III| is its operator norm. For a basis B- = (bi,...,by bp). we write ||| ||||| = max |aa| x 51 >> Or |||- (x) = xt is the pointwise ReLU. Finally, we take (c, E [0, 2 and ((a, b)) is the uniform distribution on [a, b).
Equivariance. We are interested in building equivariant networks that encode the symmetries induced by given group G as inductive biases. To act using a group we require a group representation P:G + GL(E"", which itself is a group homomorphism and satisfies p(9192) = ((g)))(()) as GL((P)) is the group of D x D invertible matrices with group operation being ordinary matrix multiplication. Let us now recall the main definition for equivariance:
Definition 2.1. Let X C RDDx and y C BDDx be two sets with action of a group G. A map f:X + y is called G-equivariant, if respects the action, i.e,, py(g) = (px(1)x)), Vy E G and x E X. A map h : X + y is called G-invariant, if h(x))= = h(px(1)a), Vy E G and x X.
As composition of equivariant functions is equivariant, to build equivariant network is sufficient to take each layer fq to be G-equivariant and utilize a G-equivariant non-linee con-linearity (e.g. pointwise ReLU). Given a vector space and a corresponding group representation we can define feature space F, == (RPi,p) Note that we can stack multiple such feature spaces in a layer, for example, the input feature space to equivariant layer can be written n. blocks F + Di F.-
2

---

Published as a conference paper at ICLR 2023
A G-equivariant basis is basis of the space of equivariant linear maps between two vector spaces. We can decompose a G-equivariant linear map f: F; - Ex41 in a corresponding equivariant basis B, = { E R D Wk [B When working with stacks of n, (resp. 7(+1) input (resp. output) feature spaces we may express the full equivariant basis by considering Kn, -1 - E 1 (p.9) E [n.] x [n(+1]], where each element Ki m441 is matrix with single non-zero entry at position (p, g). Then the basis for G-equivariant maps be- tween F,. + P1 can be written succinctly as the Kronecker product between two basis elements Rin;- & Bi Some instances of G and IF, are presented in Tab. 2. For example, in the case of CNNS with kernel size d², the linear map f is a convolution where ni; (resp. fx+11) are the number of in- put (resp. output) channels and K2,--i++ @ B is the basis of convolutions of size d² x n2 X 4
Related Work on Strong Lottery Tickets. Winning SLTs approximate target ReLU network f(x) by pruning an overparametrized ReLU network g g(x) with weights in any given layer drawn i.i.d. from w, U([-1,1); Our error metric of choice is the uniform approximation over unit ball: ma (z) [0+)|| S e, where (ax) is the subnetwork constructed from pruning g(x). Let us first consider the case of approximating a single neuron W; E [-11 1] in some layer of f fax) with i.i.d. samples X1, 11....: Xx, ~ (([-1,1)) 1]). If n O(1/c) then there exists X, that is c-close to w; (Malach et al., 2020). A similar approximation fidelity can be achieved with an exponentially smaller number of samples by not relying on just a single X, but instead subset whose sum approximates the target weight. Lueker (1 (1998); da Cunha et al. (2022a) proved that n = O(log(1 [ /c)) random variables were sufficient for the existence of solution to the random SUBSET-SUX. problem (a subset S C {I...., n such that jw; - -iis X,| I <). Pensia et al. (2020) utilize the SUBSET- SUM approach for weights dense networks resulting in logarithmic overparametrization of the width of layer in g(x). To bypass the non-linearity (ReL.U) Pensia et al. (2020) decompose the output activation a (wxx) wtx w x and approximate each term separately. With no additional assumption on the inputs (da Cunha et al. (2022b) assume positive entries), this approach fails for equivariant networks as each entry of the output of an equivariant linear map is affected by multiple input entries.
3 SLT FOR GENERAL EQUIVARIANT NETS
Our results and proof techniques build upon the
1
line of work by Pensia et al. (2020), da Cunha et al. (2022b), and Burkholz (2022a). Specifically, we rely on the SUBSET-SUM algorithm (Lueker, 1998) to aid in approximating any given parameter of the target network. Departing from prior work, the main idea used in our technical analysis is to prune an overparametrized equivariant network in way that preserves equivariance, as applying SUBSET- SUM using da Cunha et al. (2022b) construction may destroy the prunned network's 's equivariance.
[R9.A)]
Σ Enllrhaon
+
240
[R9
(R*
A
Σ Aomid
201 Aal
[R9.A)
Figure 1: General Equivariant Pruning Method
Challenges in dapting Proof Techniques. There are two major difficulties in adapting the tools first introduced in Pensia et al. (2020) to G-steerable networks. In proving the SL.TH for dense networks the relevant parameters that can be pruned are all the parameters of weight matrices, which can be intuitively understood as pruning in a canonical basis. However, such a strategy immediately fails for G-equivariant maps as the canonical basis is not generally G-equivariant, thus pruning in this basis breaks the structure of the network and its equivariance. In fact, as described in Weiler and Cesa (2019) G-equivariant linear map consists of linearly combining the elements of the equivariant basis with learned combination coefficients which are the effective parameters of the G-equivariant model. To preserve equivariance we may only prune these parameters and not any weight in ft. However, this introduces a new complication as the interaction with the ReLU becomes more challenging. da Cunha et al. (2022b) circumvent this in the special case of regular CNNs by assuming only positive inputs. In contrast, our main technical lemma (Lem. 1), introduces a construction that does not require such a restrictive assumption and generalizes the techniques of Burkholz (2022a) to G-equivariant networks.
Overparameterized Network Shape. We seek to approximate a single G-equivariant layer with two random overparameterized G-equivariant layers. We take the input ||>]|| S 1 to be
It will work with any distribution which contains uniform distribution, e.g. Gaussian, see $A
3

---

Published as a conference paper at ICLR 2023
in bounded domain to control the enror which could diverge on unbounded domains. Let F, be the set of G-equivariant linear maps F." + F.- of the i-th layer in the target network. Then, Si E Fi s.t., III S 1, is a specifie realization of target equivariant map that we will approximate- i.c. f((x) - (x( Without any loss of generality, let the coefficients of w be such that |ax| 1 when decomposed in the basis -nn-n @ Biii+1. Concretely, fi E Fi = { { = Eg ayby bx E Kn, & B lax S 1, W| II < 1}. We can now re- cursively apply the previous constructions to construct a desired Gequiivariant target network f F of depth E N. Analagously, we can define an atomic unit of our random overparameterized source model H4 as the set of G-equivariant maps with one intermediate feature space (layer) I followed by a ReL.U. That is, any h; E Hi applied to an input x can be written as ht(x)) = W o (W).). In our construction, we choose W whose equivariant basis is Bnn-tū, @ Bi where nn is the overparametrization factor of the i-th layer. We assume Bi contains the identity element, which is
2i
trivially equivariant. The basis coefficients W are written as X X which refers to the coeffi- cient of the k-th basis element in B for the map between the p-th block of F to the g-th block of F. Similarly, Wh 25+1 can be decomposed in the basis Kā.-n; B with coefficients (1 pp-g.. Fig. I illustrates this construction after pruning the first layer for n; 74++1 a "diamond" shape. We can finally apply the previous construction to build an overparametrized network h H of depth 21. We summarize all the notation used in the rest of the paper in Tab. 1.
which leads to
G-Equivariant map
Basis
Basis Coefficients
Wh: : :TT + B
Kn, Kn. @ Binss
p E g E [M.], E [[:++:]]
Wht 17 + Fi
Na. Ma:-m::11 2 Bi-ii1
Ap
p p [4].9 q E [me+a]. E [[,-+++]]]
w/ F. F
B B1-+
p [ml].9 [nes]] k [[
Table 1: Summary of notation used to decompose each G-equivariant map in the source and target networks.
3.1 THEORETICAL RESULTS
We first prove Lemma which states that with high probability a random overparametrized G- equivariant network of depth | 2 (Fig. can e-approximate any target map in F, via pruning.
Lemma 1.
Let h, E H4 be a random overparametrized G-equivariant network as defined above, with coefficients (8)
log("o n28441 Ap-g. and 11²) pg- drawn from U[[ 1)). Further suppose that each (+ where C1 is constant. Then, with probability 1 1- 5. for every target G-equivariant layer fo F. one can find two pruning masks Szi. S2i+1 on the coefficients X p and M respectively such that:
f; Cın, log(
min(e.5)
())
max KERE,
[1 @ Wh (2 O W2))) fx()]l se.
(1)
|
Proof sketch. We prune all non-identity coefficients of the basis decomposition of the first layer ob-
taining "diamond" shape (see Fig. 1 for (n, n4+1 = 1)) allowing us to bypass the pointwise ReLU. The two layers can now be used to approximate every weight of the target by solving independent SUBSET-SUM problems on the coefficients of the second layer. The full proof is provided in $B.1. O
To approximate any f in F, which is a G-equivariant target network of depth and fixed width, we can now apply Lemma l-times to obtain our main theorem, whose proof is provided in $B.2.
Theorem 1. Let h E H be a random overparametrized G-equivariant network with coef- (8) ficients X Xp-gg and up- for [1] and indices P, q, k defined in Table 1, all drawn from U([-1, 1J). Suppose that n. O2n; log( menie1 max( (.le:=ssllllBBssttll where O2 is constant. Then with probability 1 5, for every I F, one can find collection of pruning
min(e.8)
4

---

Published as a conference paper at ICLR 2023
(4) masks S21-1,... So on the coefficients X xp and u for every layer [1] such that:
|1(S211 2 W W o o Wo)x)) - f(x)]l c.
(2)
XERPOX"0, ||
We recover similar overparametriiztion as Pensia al. (2020) with respect the width of h. However, the significant improvement provided by this result is that, since we do not prune dense nets but G-equivariant ones, the number of effective parameters in the overparametrized network is //.-++//D:DDes smaller than a dense net of the same width. In section 3.2 we make this difference explicit and show Theorem is optimal up log factors not only with respect to the tolerance but also with respect to |8..++1/ p. P, 11 quantifying the expressiveness G-equivariant networks.
3.2 LOWER BOUND ON THE OVERPARAMETRIIZATON
When searching for equivariant winning tickets a natural question that arises is the optimality of the overparametrizzttoo factor n; with respect to the tolerance In the same vein Pensia et al. (2020) for MLPs, we now prove under mild assumptions that, in the equivariant setting, n; is indeed optimal (Theorem 2). We will assume that equivariant basis Bi-i+1 has the following property: Vf; E Span(B:-xc+1) where ft = Σn ogbi--it1.k we have: [lfalll S = |ax| S 1, 2 0. Note that this can be obtained by a rescaling of the basis elements. Lastly, also assume the existence of positive constants M1 and M2 such that [B-sd S M1 and n; S M2n;41- These assumptions
relatively mild and hold in the practical situations described in Tab. 2 (ef BB.3 for details). Under these assumptions we achieve the following (tight) lower bound.
Theorem 2. Let hú be network with θ parameters such that:
E SS, (0, 1) such that XERP XX1, ||x [I [(()) Sc. (3)
Then θ is at least St (1um441|B,,ao log(t)) and in is at least [m, log (+)) in Theorem I.
Proof Idea. The full proof is provided in $B.3 and relies on counting argument to compare the number pruning masks and functions in JF, within a distance of at least 2e of each other.
Thm. 2 dictates that if we wish approximate a G-equivariant network target network to e-tolerance by pruning an overparametrized arbitrary network, the latter must have at least ( log( () parameters. Applying the above result our preseribed overparametriza- tion scheme in Thm. we find our proposed strategy is optimal with respect to and almost optimal with respect to |B/++1|- We incur small extra log factor whose origin is discussed in $B.3. In the equivariant setting, the result in Pensia et al. (2020) is far from optimal as their result gives guarantees on the pruning of dense nets with similar width the G-equivariant targets which incurs an increase by a factor D / in the number of parameters. As a specific example, for overparametrized G-steerable networks (Tab. 2), we have D.D.-1/BB...4:
de G.. On images of shape I 224x244x3 with G = Cs. it corresponds to 2 4.10$ fewer "effective" parameters than a dense network. Finally, we note that Thm. 2 makes no statement which overparameetizzation strategy achieves such lower bound. Remarkably, the pruning strategy prescribed by Thm. recovers this optimal lower bound on nn meaning that, unsurprisingly, G-equivariant nets are the most suitable structure to prune.
SLT FOR SPECIFIC CHOICES OF G
In this section, we turn our focus to specific instantiations of our main theoretical results for different choices of groups. To apply Theorem 1, one simply needs to specify the group G, the group representation p(g), and finally the feature space F. For instance, we can immediately recover the results for dense networks (Pensia et al., 2020) by noticing G {e) is the trivial group with trivial action on R (see the proof in $C). In Table below we highlight different G-equivariant architectures through the framework provided in $3 before proving each setting in the remainder of the section.
4.1 A CASE STUDY WITH CNNS
As a warmup, let us consider the case of vanilla CNNs that possess translation symmetry. In this case, G Z2 +) the group of translations of the plane and D, d2 where dl is the size of a feature map
5

---

Published as a conference paper at ICLR 2023
G
P
F,
B V [|BB-N1-11]
MLP
{e}
trivial
IR
1
CNN
(z²,
fi(2 - 1)
(TR" p.)
d²
B(2)-NN
(z', x2)
pro(g)
(xr ())
x|01, ps)
d² G)
Permutation
S(n)
(R"* pp) B(ks ks41) V (n** + +1)
Table 2: Instantiations of Theorem I for different choices of G. MLP was proven in Pensia et al. (2020), CNN was proven in da Cunha et al. (2022b); Burkholz (2022a). We note a V bb= == max(a. b).
at layer i. Finally, Pr acts on the feature space R.d by translating the coordinates of point in the plane. The equivariant basis of fi in this setting (what we denoted B in the general case) are convolutions with kernels K! E R2d xnaxna11 that are built using the canonical basis and ny and m++1 are the input/output channels. We can apply Thm. to achieve Cor. 4 (see ID for details) which recov- ers Burkholz (2022a, Thm. 3.1) and is a strict generalization of the result by da Cunha et al. (2022b).
4.2 SLT FOR B(2) STEERABLE NETS
The Euclidean group E(2) is the group of isometries of the plane R2 and is defined the semi-direct product between the translation and orthogonal groups of two dimensions (R²? +) x O(2) with elements (t, g) B(2) being shifts and planar rotations flips. The most general method to build cquivariant networks for E(2) is in the framework of stecrable G-CNN's where filters are designed to be steerable with respect to the action of G' (Cohen and Welling, 2017; Weiler et al., 2018 2018). Concretely, steerable feature fields associate a D-dimensional feature vector to each point in a base space 1 + D which transform according to their induced representation [Ind (nd(2'xx (R*x))
f(x) - ([ndle"
(33 GG) p) (tg) (tg)
5) (x) = p(g) ( f(g -)) t))-
Clearly, a RGB image-a scalar trand-transformms according to the trivial representation p(g)
1, Vg E G, but intermediate layers may transform according to other representation types such as regular. As proven in Cohen et al. (2019), any equivariant linear map between steerable feature spaces transforming under pj and pi+1 must be a group convolution with G-steerable kernels satisfying the following constraint: T., (gz) = Pi+1 (g) (z) (:):: 1) Vg E G, x E B2. An equivariant basis is then composed of convolutions with a basis of equivariant kernels that we compute next.
One of the key ingredients needed to apply Theorem I is the availability of an equivariant basis with identity element. One could in principle always take an existing equivariant basis, such as the one provided by Weiler and Cesa (2019), and include an identity element by replacing the first basis element resulting in another equivariant basis with probability 1. In what follows, we show the generality of Theorem 1 by constructing a different equivariant basis from first principles via the canonical basis and then symmetrizing using the action of G < O(2). As we show in our experiments, we can find winning tickets for both basis with negligible difference in performance.
Classification of Equivariant Maps for E(2). We now seek to precisely characterize which kernels satisfy the equivariance constraint. Let R be the equivalence relation on R?,
R= = V(z, v) E R2 x R2, x a~y + 3g E G such that y - x.
The equivalence class of E IR2 denoted Ozz), is the orbit of under the action of G on R². Designate Ag = R²2 /R C R22 set of representatives. Due to the equivariance constraint on the kernels (-), once the value of π (xx) is chosen, automatically fixes <(g .)) for g x E O(x). Note
that because (z)) = [G), all possible initial matrices ||C]x|G| can be chosen at a point # 0.2
Remark. In practice. G-steerable equivariant networks do not operate on signals in R² but on fixed size pixelized grid {1, 2....... d)2 denoted as [d]2 z². Henceforth, we consider all our target networks as well as the overparameterized G-steerable network to be defined on input signals sampled on [d]2 and in appendix $E.3 we highlight two practical challenges that result from such a discretization, but crucially these do not disrupt our subsequent theory nor pruning techniques.
"Care must be taken at the origin, since Vg E G -0 0, and the set of permissible matrices depends on G well our choice of representations. We provide thorough treatment of this case in $F.2.

---

Published as a conference paper at ICLR 2023
Computing B. To explicitly build basis of the G-equivariant layers, it is illustrative to first consider the case for a single input-output pair of representations for a layer i.c. n, = R4+1 = We must first construct basis of the equivariant kernels in our domain. Let B (Bz: a E } be basis of equivariant kernels over the do- main where each basis a tensor of shape B2 C Rdxdx [G]x[GI, A single basis element b E B, can be constructed by considering the canonical basis* Ko C ||]] at each location AAR and evaluating it under the action of the group. One can freely choose both starting point x E AR, and an element of the canonical basis ~.-9. Let Kg [Bxxd][Gix] V(p, g) E
g'x
xx
s
87xx
Pail8 uM Plp
[|G]] x [[G]] be the tensor of kg stacked across the grid-i.c it is 0 everywhere except at the index (z. P. q) where
Figure Constructing K2.3
E B, for Cs-
G,
1. Then get the equivariant basis we symmetrize by acting on K0t2 while enforcing the equivariance constraint.
b(v) = G.a (v) Vy E [d]²
Σ gEG
Pit (441lg)
(6)
Repeating this procedure for all elements rig E R x|G] in the canonical basis completes the construction of our basis B2 = (Ke p.q E [[G]]]. We finally obtain a basis of the equivariant kernel as U By. G-steerable expanded kernel then simply linear combination of ZEAR
learned weights = - 0 l for each basis element- K(x) = - (x). In contrast, standard convolution kernel has shape dd x0:11 which means that the equivalent input/output channels for G-steerable convolutions are G; = |G] n, and C++1 G x n4+1 respectively. Fig. illustrates the above process for basis element for the Cs group. Equipped with this basis, which has an identity element at the origin ( (E..2). We can now apply Thm. to get:
Corollary 1. Let h E H. be a random G-steerable CNN with regular representation of depth 21, i.e. h(x) K o o.. x)) where K2. R x Kž x|G' xR.xn=-1 are equivariant kernels whose decomposition in B have coefficients drawn we have that for all f E F (whose kernels K. have parameters less than 1, and with [| < 1) there exists collection of pruning masks S2--1.... So such that, by defining K) the kernel associated with S, C W!
from 1(]-1,1]) If riş Cyn, log ( then with probability at least
min(e,5)
K 21 a (...o((k)) x)) s(x)ll
(7)
XER xPo, |
In Appendix $E, compute max(IBaettll || IIl)
that leads to the corollary above.
4.3 SLT FOR PERMUTATION EQUIVARIANT NETS
The symmetric group S, consists of all permutations that can be enacted set of cardinality The action of S, on a tensor X E Ig" " xm defined by permuting all but last index: (g X) X)
(1-.. j), Vi E S,. Any general linear permutation equivariant map W, ga*
Ba*t-1 must satisfy the following fixed point equation: +A; 1) Vec(W. = W,, where tk(k)))(+1)) the (k: + k(41) Kroenecker power of a permutation matrix P (Maron et al., 2019). General permutation equivariant networks are the concatenation of linear equivariant layers followed by pointwise non-linearities, which aligns with the setting needed to apply Theorem 1.
BB is the basis of equivariant kemnlss. B is obtained by taking the 2D convolution with these elements.
NNot that this canonical basis of the same form (but different shape) as Kag tress used for R - p
7

---

Published as a conference paper at ICLR 2023
Classification of all Linear Permutation Equivariant Maps. In Maron et al. (2019), the authors solve the above fixed point equation by first defining the equivalence relation Q on [n]] [n]] + as:
2 = Va, b E [n]] Injfettttt,, a a~ b + (Vi,j E [hi + k411, ag = aj + b. = bj).
(8)
Now for all ja E [n]]:tth+41/ / define the matrix D 1="*xx" xn such that cach entry D (o.b))w 5. Then a basis for equivariant maps is Bi = { {B*, E [m] The cardinality of this basis |Bi+i+1| = b(k; + kat1) is known as the (ki + 1;-1) Bell number and can be understood as the number of ways to partition [xx] [n]]ktttt, When Kg = ki+11 the identity element is not in the basis, therefore we replace (3......1)) by Ene(n)+/o B(aa) = 1, which is still a basis. We are now in position to apply Theorem to permutation equivariant networks.
Let E H be a random permutation equivariant network of depth 21, Le., h(x) W (..,.(((i)) where W E R=* xny equivariant layers whose decomposition in B have coefficients drawn from U([-1,1). If n, = =C2n log 2,p211 max(bi(k + +)n" then with probability at least 1 - we have minle,6)
Corollary 2.
xn=*xxxxxx xn xonxxn"xx.. W E BR xfxxnffft xns+1 are
that for all f F (with Ill S 1 and parameters in the basis less than 1) there exists a collection of pruning masks on the decomposition in the equivariant basis of the layers S21-1...., So S.L.,
max xER
|1S2111 @ W ((S @ W (x)) - -((x)] Se
(9)
||
We discuss in Appendix SF.1 the computation of [| i III. and provide the detailed proof.
Message Passing GNNs. MPGNNs networks that act graphs with n-nodes by defining feature vector for each node which is updated based on "messages" received from its neighbors which are then combined. Given node v in graph and its hidden representation x. the message passing update
EueN(.) S (x% -._1) ()) In its most general form the aggregation function fa and update function f. are taken to be MLPs. In this case it is easy to see that Theorem 1 can be applied separately to both fa independently as MLPs are captured under G = {e]. Permutation in/equivariance is trivially maintained in the pruned network as the aggregate function operates on local neighborhood of and pruning does not impact this as pruning does not impose any ordering over the nodes or the adjacency matrix in the graph.
for a layer i is governed by the following equation: x 1 (a._ I
EXPERIMENTS
We substantiate our equivariant framework to finding winning SLTs by approximating target G-steerable networks, MPGNNs, and k-order GNNs on standard image classification, node and graph classification tasks respectively. For steerable networks we consider networks for Ge {C4, Cs. D4} which are finite subgroups of 0(2). To show the generality of our framework, experiment with two different equivariant basis for B(2); the first one uses spherical harmonics and is taken from Weiler and Cesa (2019) (DEFAUL.T), while the second is the we introduce in $4.2 (OURS). MPGNNs and k-order GNNs naturally operate on S,, where permutation invariance is with respect to the node labels of given graph. For E(2)-steerable, CitRRotation-NNISS
experiment with Rotation and datasets which contain data augmentations from G < SO(2) and G < O(2) respectively ( (Weiler and Cesa, 2019). To evaluate MPGNNs and k-order GNNs consider standard node classification benchmarks in citation networks in Cora and CiteSeer (Sen et al., 2008) and real-world graph classification datasets in Proteins and NCI1 (Yanardag and Vishwanathan, 2015).
We find equivariant strong lottery tickets by utilizing our overparametrization strategy described in $3 by solving SUBSET- SUBSE---UM problems using Gurobi (Gurobi Optimization, 2018). The definition of the SURSET-SUM problems as mixed-integer optimization problems can be found in eq. 28 of SG. In Table 3 we report our main results for overparametrization constant C (see Thm. 1) towards approximating a single target network using 5 random seeds to construct our overparametrized network. Specifically,
report the ratio of the number of parameters in the overparametrized and
$1 (n.))nn if (a, b) E z and otherwise, for E [m]* and E [m] 4+4
8

---

Published as a conference paper at ICLR 2023
final pruned network divided by the original target network. We also report test accuracies for both, the maximum absolute weight error over all SUBSET-SUn problems, and the maximum relative output error between pruned and target networks. All model architectures and described in $G.
For all equivariant architectures and datasets considered, we find that we are able to approximate the corresponding trained target networks sufficiently well. Specifically, we achieve sufficiently low maximum relative output error across test samples such that the test accuracy of the resulting pruned network matches essentially that of the target one for all random seeds of the pruning experiments. Finally, we conduct an ablation study on the effect of overparametrization constant factor C' to the approximation accuracy with respect to the tolerance e. We perform this study for the B(2) equivariant architectures for different subgroups. In Fig. we plot this as a function of C' {1, 2, 5, 10} for the groups C2. Cs. D4 using the basis construction from Weiler and Cesa (2019). As observed, increasing our overparametrization factor leads, up to = 5, to a lower maximum relative output error while the pruned accuracy marginally increases.
C
C2
D2
Moximum Relstive
#359
8.35-
6375-
2585
0.0-
0,33
566-
8339-
Pau Relation
E.00-
Mac Relaiin Out Dr
Pruned Accumey
-0395
00903
8.499
0.00
0.00
10
Figure 3: Ablation study of max. relative output error and pruned accuracy w.r.t. to C for Cs, Ca, Da.
Task
Ratio s/mraes
Accuracy (%)
Errors
Arch.
Dataset
overparam.
pruned
targel
pruned
param.
output
MPGNN
Cora
2.0c
99.1
80.2
80.2
6.2c + 3.3e
3.7e 0.5e
CiteScer"
5.5e 4
103.8
63.4
63.4
1.1e
4 1.76 -1
1.8e 1.7e
o-nner GNN"
Proteins
3.6c
51.8
81.08
81.08
1.2c-4
1: 4.2c-5
8.8c 2.9e
NCI1
5.3e 3
85.9
71.21
71.21
8.1e + 5.2e
2.6r 3 9.99
D2-C-DEFAULL
3.0c²
41.0
97.7
97.7
1.4e 0.0e
2.7e 3 +.4e
E2-CH-DEPAULT
Rot-
3.1e²
41.2
98.1
98.1
1.2 # 0.2e
1.9c +
E2-C4-OURS
MNIST
2.9c²
122.3
96
96.2
6.2e + 5.
2.4e 0.3e""
F2-CH-OURS*
3.0c²
120.9
96.8
96.8
2.1e + 0.6e
3.3e 3.7e
E2 12-DI-DEFUULT
FlipRot-
3.1c²
77.0
96.3
96.3
4.1e-2
1 4.2e-2
1.4e- 1: 1.1e-
E2.D4. D4-OUSS
MNIST
3.1c²
115.4
94.1
94.1
2.4c 1 0.9e
4.2c 1 1.2c
Table 3:
Pruning random overparameterized G-equivariant networks to approximate G-equivariant targets. We report a) 8/Puses the parameter ratio of the number of parameters p the overparametrized or the final pruned networks over Pures. b) the test accuracy the target and the pruned networks, c) the maximum absolute weight error over subset sum problems, d) and the relative output errors of the pruned network in contrast to the target over samples in the test set. STDs are below 1e 4 "Maximum time of MIP solver for SUBSET-SUM problems was thresholded to 600ms.
6 DISCUSSION
This paper introduces a unifying framework to prove the strong lottery ticket hypothesis for gen- eral equivariant networks. We prove the existence with high probability of winning tickets for randomly (logarithmically) overparameterized networks with double the depth. We also theoretically demonstrate such an overparametrization scheme is optimal function of the tolerance. While our presented theory is built using overparametrized networks of depth 2T. it may be possible to extend Theorem 1 to the setting where overparamatrized networks have depth L. + 1 as in Burkholz (2022b) by adapting the proof techniques. We leave this extension as future work. Our framework enjoys broad applicability to MLPs, CNNs, E(2)-steerable steerable networks, general permutation equivariant networks, and MPGNNs all of which become insightful corollaries of our main theoretical result. One limitation of our developed theory is the assumption of using point-wis, ReLU as the non- linearity. As a result, a natural direction for future work is to consider extensions of the SUBSET- SUM problem beyond linear functions more general non-linearities. In addition, our overparametrization strategy employed the "diamond shape" technique; however other schemes might also yield an optimal upper bound, Characterizing these schemes is exciting direction for future work.

---

Published as a conference paper at ICLR 2023
7 ETHICS STATEMENT
The main contributions of this work are primarily theoretical in nature seek to provide general framework to study equivariant lottery tickets. Consequently, any potential societal impact would necessarily be speculative in nature and deeply tied to a particular application domain. For example, one could consider the environmental cost savings from creating an overparametrized G-equivariant network that does not need any GPU hours train, but instead CPU resources to solve SUBSET-SUM problems. Beyond these goals any application of our theory to actual practice is likely to inherit the complex broader impacts native to the problem domain and encourage practitioners to exercise due caution in their efforts.
REPRODUCIBILITY STATEMENT
We provide complete proofs for all our theoretical results in the Appendix. In particular, proofs for Lemma can be found Appendix B.1 and Theorem is direct application of this result [-times and whose proof is located in B.2. The proof for Theorem 2 is located in Appendix B.3. Furthermore, instantiations of framework for E(2) -tterrable CNNs, permuation equivariant networks, MLPs, and vanilla CNNs resulting in corollaries 1, 2, 3, and 4 respectively. The proofs for all the corollaries located in Appendices (MLP), D (CNN), E.4 (E(2)-CNN), and F.I (permutation equivariant networks). We provide full details on our experimental setup, including hyperparamters choices, architectures, and the exact SUBSET-SUM problem being solved for pruning Appendix G. Finally, code to reproduce our experimental results can be found in submission's 's supplementary material.
ACKNOWLEDGEMENT
The authors would like to thank Louis Pascal Xhonneux, Mandana Samiei, Mehrnaz Mofakhami, and Tara Akhound-Sadegh for insightful feedback on early drafts of this work. In addition, the authors thank Riashat Islam, Manuel Del Verme, Mandana Samiei, and Andjela Mladenovic for their generous sharing of computational resources. AJB is supported by the IVADO Ph.D. Fellowship.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
D. Blalock, J. J. Gonzalez Ortiz, J. Frankle, and J. Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2020. (Cited on page
R. Burkholz. Convolutional and residual networks provably contain lottery tickets. arXiv preprini arXiv:2205.02333, 2022a. (Cited on pages 1, 2, 3, 6, and 22)
R. Burkholz. Most activation functions can win the lottery without excessive depth. arXiv preprint 02f::2205502.321, 2022b. (Cited on pages and 9)
R. Burkholz, N. Laha, Mukherjee, and Gotovos, On the existence of universal lottery tickets. In ICLR, 2022. (Cited on page 2)
T. S. Cohen and M. Welling. Steerable CNNs. In /CLR, 2017. (Cited on page 6)
T. S. Cohen, M. Geiger, and M. Weiler. A general theory of equivariant CNNs on homogeneous spaces. NeurIPS, 2019. (Cited on page 6)
A. da Cunha, Amore, F. Giroire, H. Lesfari, Natale, and L. Viennot. Revisiting the random subset sum problem. arXiv, 2022a. (Cited page 3)
A. da Cunha, E. Natale, and L. Viennot. Proving the strong lottery ticket hypothesis for convolutional neural networks. ICLR, 2022b. (Cited on pages 1, 2, 3, 6, 22, and 25)
L. Deng, G. Li, S. Han, L. Shi, and Y. Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 2020. (Cited on page
J. Fischer and R. Burkholz. Towards strong pruning for lottery tickets with non-zero biases. arXiv preprint Ar.i:22 11.00.1111,,,01 150, 2021. (Cited on page 2)
J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2019. (Cited on page 1)
L. Gurobi Optimization. Gurobi optimizer reference manual, 2018. (Cited page 8)
L. He, Chen, Y. Dong, Y. Wang, Lin, et al. Efficient equivariant network. NeurIPS, 2021. (Cited on page 2)
G. S. Lucker. Exponentially small bounds on the expected optimum of the partition and subset sum problems. Random Structures & Algorithms, 12(1):51-62, 1998. (Cited on pages 3, 13, 14)
E. Malach, G. Yehudai. S. Shalev-Schwartz, and Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In ICML, 2020. (Cited on pages 2 and 3)
H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In ICLR, 2019. (Cited on pages and 26)
Orseau, M. Hutter, and Rivasplata. Logarithmic pruning is all you need. NeurlPS, 2020. (Cited on page 2)
A. Pensia, S. Rajput, A. Nagle, H. Vishwakarma, and D. Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over-parament peeererramttiinotooonn is sufficient. Advances Neural Information Processing Systems, 2020. (Cited on pages 2, 3. 13, 19, 21, and 27)
V. Ramanujan, M. Wortsman, A. Kembhavi, A. Farhadi, and M. Rastegari. What's hidden in randomly weighted neural network? In CVPR, 2020. (Cited on page 1)
Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification in network data. Al magazine, 2008. (Cited on page
K. Sreenivasan, S. Rajput, J.-Y. Sohn, and D. Papailiopoulos. Finding nearly everything within random binary networks. In AISTATS, 2022. (Cited on page 21)
R. Vershynin. High-diimnsional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018. (Cited on page 20)
11

---

Published as a conference paper at ICLR 2023
M. Weiler and G. Cesa. General -queevarrrt steerable CNNSs. NeurIPS, 32, 2019. (Cited on pages 2, 3, 6, 8, 9, 23, and 24)
M. Weiler, F. A. Hamprecht, and M. Storath. Learning steerable filters for rotation equivariant CNNs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018. (Cited on page 6)
P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015, (Cited on page 8)
12

---

Published as a conference paper at ICLR 2023
A ADDITIONAL MATERIAL ON THE SUBSET SUM PROBLEM
We recall here some results on subset sum originally from Lucker (1998) and modified by Pensia al. (2020) to better fit the proof.
Lemma 2 (SUBSET-SUM lemma). Let U ~ U((O, 1J) (or u([-1,0) and V ~ u[{=1,1) be two independent random variables. Let P be the distribution of UV. Let 6g be the dirac-delta function. Define distribution D = 200 + P.P. Let X1....X, Xx, be i.i.d. from the distribution D where C' Colo(( ()) (for some universal constant C). Then, with probability at least 6, we have
V2 E [-111] [n] such that
Exlsc ÉS
(10)
This Lemma, in fact consequence of the corollary 3.3 from Lucker (1998) which states that as distribution contains uniform distribution, one achieve any target with exponentially small precision by SUBSET-SUM.
Extension to more general distributions. This allows us to extend the result Theorem to more general setting, where the distribution of the random coefficients is not ([[-1,1] but contains a uniform distribution.
Let's say that a distribution Z contains a uniform distribution 4([a, b]) if there exist a distribution Z and constant E [0, 1[ such that:
Z (Z1 +1 ([, 6])
We want extend the results of theorem to distributions containing U[[ a]) for some
We follow therefore the same path as in Pensia al. (2020) to prove Lemma 2 but with more general distributions. Pensia et al. (2020) already made remark for this next extension that we state and prove here.
Lemma 3. Let O. Let X and Y be two independent random variables such that contains u((0, a)) (or M([_a,[[]))) 0I)) and Y contains u([ al). Then the PDF of the random variable XY is such that:
a²
=A. > 0, fxy 2 Ag log
for|2| < a²
Proof. By the change of variable X and x one can apply lemma from Pensia et al. (2020) to get that if X ~ ~u(10, a)) (or (([=a, and V ~ u([aa, a]] the PDF of XÝ is:
a²
log 2a
if | < a² and 0 otherwise
[z]
Now we know by hypothesis that Jox, ay > 0 such that fx 2 ax axx(o(()))) and fy 2 ay full-a,)))
Therefore, fxy 2 exxafxx and finally, fxv 2
Log
(5))
if 1 5
20t
Lemma Let and be two independent random variables such that X contains U((0, a)) (or u([aa, 0l)) and Y contains u([-a, al). Let P be the distribution of XY. .. Then there exists distribution and a scalar Bg such that:
á 2
P B.u(
+ (1 B.)Q
2'2
Proof. This is direct consequence the lower bound on the PDF of XY that was shown in the previous Lemma.
13

---

Published as a conference paper at ICLR 2023
Using Lemma 4 and Corollary 3.3 from Lueker (1998) leads immediately to the following result:
Lemma 5. Let > O. X be a random variable containing U([0, al) (or u([=a, 0J)) and Y containing U([_a, al). Let XI,..., Xn be iid random variables following the distribution 2 + P where P is the distribution of XY. Then, if n z Ca log (2) (for some constant depending on a.,, with probability least C. we have:
42 E [-1111 {1, (I,...,m n) 12
Exilsc
SES
Proof. This follows immediately from Corollary 3.3 in Lucker (1998) (by applying Markov's in- equality) and Lemma 4.
Discussion. This allows to generalize Theorem to settings where the random overparametrized
network has weights taken from a distribution which contains U([-a, al). This includes almost all the usual settings, namely Gaussian, uniform. ... Indeed, the only thing to change is to no longer use Lemma 2 but Lemma at the same place the proof and by assuming that the distribution of the parameters of the overparametrized network contains (1[[a, al) for some 0.
B PROOF OF THE GENERAL SLT ON EQUIVARIANT NETWORKS USING POINTWISE RELU
B.1 APPROXIMATION OF AN EQUIVARIANT TARGET LAYER
We now prove Lemma that is used approximate single layer in G-equivariant target model.
Lel hi E Hi be a random overparamelrized G-equivariant network as defined above, with coefficients ( Ap-g.k and p pp- drawn from U[[11, 1]). Further suppose that each
Lemma 1.
ì. Cin, log( Dins+1 max (B:-i41 111-,,1,,,, where C₁ is constant. Then, with probability min(e.A)
1- for every targer G-equivariant layer f. Fs, one can find two pruning masks S2i. S25+1 on the coefficients X p s and Mp respectively such that:
(0)
max XENDE
11 O W2 o Wh)x) f((x)l sc.
(1)
|
Proof. Let us first recall that the main hypothesis needed for this lemma is to have an identity element in the basis B We note that this very mild assumption since the identity is trivially equivariant between F; and F; and one can always choose to incorporate it in the basis. Consequently, we will designate the first element our equivariant basis to be the identity b;- T.
Remark. We choose C₁ = 3C' to ensure that (C' is the universal constant introduced in lemma 2):
n,4+1 max (|B,+++1l, B++++1lll) C' loo [4n,1441 max (BB ||
C₁ log
min (e, 5)
min (c,
which is true for the entire domain of variables we are interested in (ni, ni+11
> 1, 1, S and [B,+44|| 2 1). It easy to that 3 3lgg(x) > log(44) [2, +oo| 3 4r in this domain.
To begin, first introduce function, X. identify blocks in feature space F.. In par- ticular, we leverage the "diamond shape" structure (see Fig 1) and define X [ū,] - [n.]. such that it divides the intermediate layer of overparametrized approximation into groups of G2 log( aime max([88 1 s(لa)l))) blocks which are linked with the same block the first (i-th) minle.d)
layer. In other words, x associates block in Ro: in surjective manner block in Fm; In last piece notation we will use v. to mean the w-th block of the feature space for x. For example, if RR x which is contained in the feature space Fh of the i-th layer then [m.] and x.
14

---

Published as a conference paper at ICLR 2023
denotes the w-th vector of dimension D; in Finally, because is dummy index, quite often will replace it with appropriate layer index e.g. p. r. With this in hand we can write the function (4) as follows:
X(g)=
q Ci log BoRttt max BI min(c,
+1
B
Before pruning, one has
84 B
W 21
(w ni @ bp-aa
We begin pruning by annihilating all first layer coefficients not associated with the identity basis element (k + 1) A p and for q & x (p). This yields the following decomposition post-pruning,
Ri
W
p=1 9EX g=1 (p)
Note that we can write p = x(g) leading to the following:
(W 2: = (8)
1 xx(o)
After the a, -ic the pointwise-ReLU, one then has:
a aW 2 (21 x(x) -q.1 x
10+ x(1) x(1) + x(9) x x(x)
x
+ (0)
where used the fact that the ReLU is pointwise and the identity scalars o owzz) w x w x Expanding the second layer in its equivariant basis and using the above equation we get:
dc
18 1
W 24+1 0 (W
=
Σ
b oWWh,)),
(11)
R2
Σ
(200t + + x, (12)
p=1 gEX (p)
18 181-
(1 A biitt1
(13)
(EX-1(p)
|8 man
Σ
(1) (1)- (u
(14)
9EX-1(p) (p)
Our goal is to approximate the target model whose r-th block can be written as:
na
Rs sarl
f(xx),
(8) g
b
(
term
term
15

---

Published as a conference paper at ICLR 2023
To do so, we only have to approximate ap-rr, in term 1, for all p, r, k, using subset sum of
(8)
(x) (e (++ and Op-rr, in term 2, by subset sum of Egx
This can be achieved by judiciously choosing pruning masks that selectively include (1 u which is a by-product of solving independent SUBSET-SUM problems.
The key insight powering our analysis is to notice that the variables (6)
up-tr. that appear in each approximation problems are different if (p, r. k) # (p', rr, Moreover, the two different problems for fixed indices (p, k) can be seen using different variables since following whether positive or negative,
(6) pp+g.1 will necessarily be O in the first or the second term equation. Therefore, either
in the first or the second equation, Pg-an, can be seen as being not a variable of the SUBSET-SUM problem. We are then at liberty to decide whether to prune the variable or not in the equation where appears, because the pruning of the variable will not affect the result of the other SUBSET-SUM problem. Following this approach, we can then find a mask on the variables implied in subsequent problems, solve the problems independently and finally take the concatenation of all the masks in the second layer which will simultaneously solve all the problems.
We now quantify this approach by showing that with high probability. the 2n, (B subset sum problems (with independent variables) written below can all be solved by applying a pruning mask on the second layer. The pruned mask applied on the second layer denoted S2 q-rrk
{0, 1 1 x x|B,->i-1,, al, The subset problems are written below:
(4) Jerr
Σ
(S o oug (1) ( p - ( apor v(p,r,k) E [ns] x [ma+]] x [B,
pork
(EX-1(p)
2n,14+11 max (rax((Biisii Bi-si-1ll)
and
Jerr
Σ (S
q-rrk o (1) 1
p-ga - Oponk r(p,r,k) E [m:] x [nai] x [[B,i+t]]
pork
9EX (p)
2n,4i+1 max B.i+til
We will now use the SUBSET-SUM Lemma 2 which explains the overparameeriizatoon that one needs to solve the SUBSET-SUM problems. Since ((()) pg and ((0) pp-2.. are i.i.d following ([[-1, 1]).
Ap-2.11 follows _ō + jU with the notations of lemma 2. We deduce that the Mo p are p-
(+)+
ii.d. following the distribution
_ + P.P. This is the same for u p-9g.1 which are i..d. following the distribution D = 10 J.. Here should note that Vp E (p)
(i) (0)-
C log( (.24+11 max! ( 1.1 -++,,,+++))) Therefore, by using lemma 2, V(p,r, k) E [md] x [m+ti] x min(e.d)
[[[,++1]], the two subset sum problems can be achieved by pruning the coefficients (6 Mg with maall Call this the event FX(1) F By taking the
probability at least 1 20,ns
(() intersection the events, we get that ( (err) sanill ptrk holds with probability at least,
8
p(E(0) = n 2ng1541 max [B .i 11 B B
21-6
"At this point one may prove the same lemma but with more general distributions on the coefficients (6) and (.()) gg k by assuming that they only contain 44[[aa, al) for some >> 0 and by using Lemma 5 instead of Lemma
A
16

---

Published as a conference paper at ICLR 2023
In other words, with probability least 1 6, all the SUbsET-Sune problems are solved. Finally, remains to check that the approximation holds with this pruning mask. Let be defined as:
Ω = max 2[ O w W2+1)0((S2 O w2 fi(x)l-
|
By applying the masks we get:
max max ||(Se41 & 20 O x2,)),, - fa(x)r]l
re(n++]]
|||||]
n B8 11-11
(0) (aporcc + t )bs )bi (a (ap-r + terrome )
max re[mu4]]
max
|
B
p-trk bi bo (1 (ommsl-siaa |I
kml
B B
B Be-itl
$ max
Σ k=1
err p +
err (1)
p-rk, b b((+11(((
rE [1+41] p=1
B. B
B B
< max rE[n.+1]
max |
err p b b(-5t1n(27))
+
max
err p by bi
$1
k=1
k=1
1B m1al Σ
18 1i11l
< max
erT p bi bi
+
Σ
err p-rkk bi b(
re(n;11]
p=1
Ri
2x
x Bi++ill
2n,0+41 max B B-(+illl
1=
<
Note. In the statement of the Lemma used specific choice of norm (lp) but proof strategy will work with every norm as soon as a, the ReLU non-linearity. is 1 1-Lipschitz (which may not be the case for some esoteric norms). As result, there is need to restrict oneself to the -nomm, though for ease of exposition and not to confuse the reader we made this choice above. Moreover thanks to the flexibility of the SUBSET-S SUM theorem, the proof can also be extended to milder hypothesis which is on the distribution of coefficients. Specifically, it is sufficient to have that the distribution contains a uniform distribution centered at 0 (see Lemma 5). The immediate consequence of this that it is possible to accommodate other weight initialization schemes that are commonly used in practice, but again for ease of readibility we chose Uniform distribution.
B.2 APPROXIMATION OF EQUIVARIANT TARGET NETWORK
We now prove in this appendix Theorem which approximates a full target model. We first recall the two main assumptions (very mild) that are needed for the Theorem statement:
Il E Bi++
* a the pointwise ReLU is used as an equivariant nonlincarity and is 1-Lipschitz.
Theorem 1. Let h E H be a random overparametrized G-equivariant network with coef- ficients X X and poprg, for [1] and indices p, q, k defined in Table 1, all drawn from U([-1,1] 1]). Suppose that n. C2ng log( Beai44 max( B. 1.1. 1|B,,+++11 where Oz is minte.8)
(8)
constant. Then with probability 1 - 8, for every F. one can find collection of pruning
17

---

Published as a conference paper at ICLR 2023
masks 121-1,... So on the coefficients X xp and (4)
1 for every layer such that:
xERPox"0, | ||(S211 2 W 2 ((.. o Wo)x)) f(x)]( ce
(2)
Proof. We first note that different constant C2 2C1 in the theorem compared to lemma which helps ensure that,
O2n; log n,4++1 max ([B IIB B| (111)1)))))) 2 Cyn log 22, max min (c,
(BB,-++1) I| B )
min (e, 8)
which is true in the domain of the following variables (n,, M441, 2 log(2)) 2 log(2z) on [2, too].
1,8 S, 2. B 1)
We first apply lemma I-times for each layer of the target network with e becoming ş) and becoming
7. With an overparametrization factor n. Cin, log( 2n, max 1111 we get that for each layer i,
min(c.5)
| [[(2++1 (241)0((S2 @ W fx(x)]
(15)
27
holds with probability at least 1 - 5. By taking union bound, we get that this holds for every layer with probability at least 1 6. Now, let x be the input to the (2i)-th layer of the pruned overparametrized network h. Furthermore, let be the input to the i-th layer of the target network f. Then we have,
r 30 x
2/ ((S2+1 Wh 2 ((22 Wx)x() for irisle 5-1-2
o = (Su-1 @ Wh 1 2( 3 Wh (
Equation 15 implies that,
(Sa411 C 12 C wh)x()
f((x))l < |*|| 21
(16)
Passing through the point-wise ReLU which is 1-Lipschitz for all the norms that we work with we get:
[ s |x||| ++ 2
(17)
By leveraging a recursive argument, and using the fact that ||*||| ||||| S 1 we then get that for all i 1}, || S (1 ). Then, forall S
|x44
Xi+1
||o ((22+1 O W w ( w a (fixs))
|| (S2441 @ Wh N241)0((S)) w2) (I(xx)) (((()))))))))))))))))))))))))))) (f((z)) II
|x||| + ||| x
+ 21
||x
x ||
where used the fact that is Lipschitz. We then get that,
18

---

Published as a conference paper at ICLR 2023
| - zı| = 21(S2/1 & W Jo ((S o W
2S + 22
- - (|fr-((x(1)) - fi- (x
$ |
+ f ||| x/-1 - x1-
21
< +
6
)
6
+ |||__ -1-1ll
21
21
(1 c)²
21
21
(1 ) -1
21
$ 5
1 2
Se because
B.3 LOWER BOUND
We now prove Theorem 2.
Theorem Let by be network with è parameters such that:
F. SSE E (0,1) such that
max
[I ( - f((x) se. (3)
xERP,X" XX ||
Then O is at least Q (n:m++1 (Ba log( ()) and in is at least D(n, log (t)) in Theorem I.
Let us first recall the main assumptions of our setting:
For all fi E Span(Kn.-muz & Bi+ii1),, where f. = Epennd Ege(na. Σx Pp-g. bi we I 1. This assumption extremely mild as can always trivially be satisfied by rescaling the basis elements.
have: ||l < = (
=
3M1 E R such that, uniformly over for every possible building block in our equivariant feature spaces F, and Fi+1 have, |B,+s| M. This assumption is used mainly guard against a non-trivial scenario where the first layer would be able to carry "a lot of superfluous parameters". This assumption finds its solitary parametrization factor the theorem 1, i.c to prove ñ, 2 Q(n, log (2)) and is not used for the lower bound on O. This assumption is very mild because in most of the usual cases (MLPs, CNNs, E(2)-steerable CNNs) the possible building blocks of each layer F, are finite (respectively R, Rdd and d or ( Being finite automatically implics the existence of such a constant M1 as we can simply take the maximum over the possible values of |8--+11
in achieving the lower bound
the over-
[B...
Finally we assume the existence of a constant M2 E such that n, M2n1+1- This mild assumption-lit the previous one-is used to ensure that n. D(n, log (?)).
Our proof relies on a counting based argument that compares the number of pruning masks to cardinal of 2e-separated net P in the set of target networks with respect the operator norm. A similar argument was used by Pensia et al. (2020) in the context of dense nets. We recall here the definition of 2e-separated net:
Definition B.1. Let be a normed vector space. 2e-separated net P, in F subset P C F such that:
121 E P.
2 + x2 = || x221
In Lemma 1, we considered only set of target network F; C Span ( & B where each function has [|ll and || < 1. Mixing this with the first assumption written
19

---

Published as a conference paper at ICLR 2023
above, it is therefore the set of maps fi such that ||a I 1. Now consider the isomorphism I Span(An, @ BB-++1) Ro Bi-ital, which identify function with its coefficients in the equivariant basis.
I = S
(18)
This isomorphism shows that Fi can be seen as the norm ball of 1 with respect to the norm induced on R 1a/5; siial by the isomorphism. Moreover P a 2e-separated net on F; if and only its image is 2e-separated net on RR [B,-++]| with respect to the induced norm.
Lower bound on [P]. We just need to use Lemma 4.2.8 and extend Proposition 4.2. from Vershynin (2018) to non-Euclidean balls. The general idea as follows: Denote by (zx, R) the ball centered of radius R in I 1 [8, 11 and by μ the Lebesgue measure. Let us construct a 2e-separated net as follow: we take for first point the origin 0 of the vector space. At the step n. to construct the + 1-th point of P we proceed as follow: if ((0, 1) CUZEP ((x, 2t) we stop the processus and don't ot take any 1-th point. Else, we take point in B(O, 1) U (ax, 2e). We know that this point is at distance of at least 2e of the other points of P. Moreover it is in the unit ball. At the end of the process (which must end since the unit ball is compact), we finally get that for the 2e-separated net P. ((0, 1) C UPEP (xx 2c). Therefore, (B 1)) I n(USEp B(x, 2c)) I [ 2c) Finally, [P] 2 ((B(U.1)
((B(0,2)) = (2e) (2) m In the last step, we use the fact that the Lebesgue measure of ball of radius R in vector space of dimension is R"V, where V, is the Lebesgue (:
measure of the unit ball. This allows to choose (P] 2
2c
Lower bound induced θ. As the network that seek to prune has Q parameters, the number of binary pruning masks that can be constructed 2 Moreover, due to the triangular inequality, each pruned network approximate at most one element of P. Indeed, if f! + f? P are approximated with the same pruning mask,
1s f!1l < IIʃ? ( + (1S @ hv) fi1l S 26,
(19)
which contradicts the fact that P is 2c-separated net. This directly implies that the number of pruning masks must be bigger than the cardinal P.
( 1
7, (B.++1/B.-4411
2 2
(20)
2c
and by taking the log,
n,71; /
BBti
log
(21)
log(2)
2e
which shows that O must be at least 0( B log (+))
Lower bound on 7. We now seek to provide a lower bound n. such that Theorem 1 holds. Since, our main claim requires that we approximate every target network with probability at least 1 - > 0. the set of parameters (drawn from any distribution) that achieve this is non zero. What remains is to count the number of parameters contained within the overparametrized G-equivariant network in H4 (see Lemma 1) function of the overparametrization factor ñς. This allows us lower bound n, via the lower bound on the number of parameters established above. Now any overparametrized G-equivariant network we construct has the following number of parameters:
Number of parameters of the first layer: n, n,ūū Bx
Number of parameters of the second layer: i, [B,+++1|
Therefore the overparametrized network h; has θ (, + n441 1 parameters. Using the second and third assumptions, we get that:
θ < M2n BB + n (Brl)))) (M, + M00MM22114444lll 1)
(22)
20

---

Published as a conference paper at ICLR 2023
Moreover by Eq. 21, we know that:
)
+ 2 S2 1B log
therefore implies that:
-
iu 2 Q ny log
(23)
Discussion. Using the result in Theorem 2 we can now understand that Theorem informs us that our proposed overparametrization strategy is optimal with respect to the tolerance e and al- most optimal with respect ne74++1 1- In Theorem I observe additional factor of (og(m;n4++ max( || which appears in ňz We can reconcile this term which appears in the proof due to both our choice of with which metric do want to approximate the target network and to the probabilistic setting of the SLTH.
Indeed, first note that chose to approximate each target layer by with respect to the operator norm associated with the norms on the input and output space. But such a choice is arbitrary, and if we had chosen another metric, such approximating each weight of the target network in the diamond shape structure by e, then the term n,M44+1 B I|| might have been eliminated.
The term n,74++1 [Ba++1 arises from the fact that the parameters of the overparametrized network are drawn from a random process. Specifically, a bigger overparametrization needed because of the scenario when not all the SUBSET-SUM, problems have solutions, which has probability of occurring that grows with n,74+1|B,, / -ie.. the complexity of the approximation. We could replace the probabilistic setting by instead taking overparametrized network deterministically initilized by a smart initialization such that with probability one all possible subnetworks can be obtained by pruning the overparametrized one. In this case, the overparametrization would no longer have the term n,7,+1 [B,++1l in the log. Such an initialization can be taken for example by decomposing the overparametrized network in the different blocks of the diamond shape
the width
(the weights that not part of a diamond shape can be initialized freely). Each weight of the target network can then be approximated by pruning the diamond shape with mask which is the binary writing of the target weight. This is possible for every weight of the target network and for all target network at once with probability one (with different mask for each target network). We note here the similarity of this construction with the one used in Sreenivasan et al. (2022), albeit under a different setting than the one we considered here.
and taking the weights in each block to be =1, #1 +1 +(3)
(
logie)
In conclusion, we give some hints to annihilate the term 74744 max([B, 1, B II]) first choosing another metric for approximating a layer and secondly going to non-probaiiliitic setting where the overparametrized network smartly initialized.
C PROOF OF STL ON MLP USING THEOREM
This corollary recovers the main result of Pensia et al. (2020).
In this case, G = {e) and the representation is trivial. The building block of a layer is F; IR and each layer composed of a stack of n,, i.e. R = FT. The norm that we will use on R is of course the absolute value Therefore, as explained above, the norm that we consider on F. R. is || bo.e. The pointwise ReLU is trivially equivariant, since the G is trivial. It is moreover 1-Lipschitz.
All maps are equivariant, since the group G' is trivial. An equivariant basis of the maps FF - F Fi+1 and of the maps F. + F, therefore basis of the maps I - IR. is of dimension and of course taken to be the identity. We therefore obtain that the identity is in B One has |B, = 1 and ||
max ||]]]]
All the conditions are therefore validated and we are free to apply Theorem in this setting, with max( || III) 1 which leads the following corollary:
21

---

Published as a conference paper at ICLR 2023
Corollary 3. Let h H be random MLP of depth 21, i.e., h(x) W 21 10t (... (W6)))
where Wht E R W
21+1 1 are dense linear maps with weights drawn from
u[(-1,1) If C2ny log f E F target MLP with layers W E E[-1, 1| and filll - 1 there exists collection of pruning masks 121-1,...;55 So such that,
1:2; 112) then with probability least 8 we have that for all minn(e,))
max XER* ||
||(S2-1 O W W2-110 (...o ((So @ w x)) f(x)) se
(24)
D PROOF OF SLT ON CNN USING THEOREM
We now prove Theorem application to the case regular translation equivariant CNNs. We highlight here that this is strict generalization of the result obtained by da Cunha al. (2022b) do not assume strictly positive inputs (recently extended in parallel Burkholz (2022a))-
Corollary 4. Let h E H be random CNN of depth 21, i.e., h(x) = K # (... o (Kls x)) where K/ E TR xn, K E RRd xhx xa are convolutional kernels with weights in 4II-1, Ifri = C2n, log all E F a target CNN with kernels K/ E [-1,1] xn, x and Illfell S there exists a collection of pruning masks S21-1..... So such that,
d denmeeat min(e.8) ) then with probability at least 1 - 8 we have that for
max xERd Xma, S
11 O 1)-1) (...o ((So O Kb) x)) f())l sc
(25)
We now prove Corollary In our case, the building blocks of every layer are FF; Rdd where df is the size an image. Therefore, B is the basis of translation equivariant maps: Rd + R When working with CNNs, the basis that is used in practice is the convolution with kernel K E Rdd where KP-9 has only where (p. q) E [d]2. It is therefore easy to see that
the index (p, q) and is filled everywhere else with zeros on the grid
B d²
Let us choose || lloo as norm on Rdd Applying the proposition I from da Cunha et al. (2022b), get:
VK
dxd
VX E Raxd
|K x 0
K |X|
By using this basis we then get that,
||
|||
max
max
KK X
KE]-
max
max
| X
KE
X
< d²
We then get that:
max((B.-+t1l: 11 &
is trivial to notice that the Pointwise-RelUU used is equivariant and 1-Lipschitz. Moreover, the identity is clearly in Bi-; by taking the kernel with only 1 at the origin. Therefore all the conditions
22

---

Published as a conference paper at ICLR 2023
met and we can apply theorem
which states that the overparamettrization needed is:
n,44+1 max
(|B,+ ||,,,+++++
i4 C2n; log
min (c,
&dnmiial min (e,
C2n4 log
E ADDITIONAL MATERIAL ON B(2) (TE)RREEE NETWORKS
E.1 GENERAL EQUIVARIANT LAYERS IN THE CASE OF FEATURE FIELDS DEFINED ON IR.
In full generality, the theory of E steerrabee CNN has been developed in the setting of continuous and infinite steerable fields defined on IR2 The input and output of a layer are then respectively functions in (IR² + I) and in (R2 R ). The reader will immediately note that it does not correspond to the practical case of -tteerabe CNN since these type of inputs are not infinite dimensional. The condition for layer to be equivariant between these two feature fields is to be written as a continuous convolution with kernels satisfying the condition (called equivariant kernels):
T(g x) = (oui(g) (T) (m)) (g), Vg G, X
(26)
There are different methods to compute the possible kernels that satisfy this condition, that will lead different basis. For example, in Weiler and Cesa (2019), the authors use the polar coordinates to solve this condition. They have a free parameter which is the frequency and by varying this parameter they can compute basis of the equivariant kernels.
Our method to construct a basis of the equívariant kernels is different: we quotient the plane R² by the equivalence relation induced by the orbits under the group G. For each point in the continuous quotient space AR, we compute a hasis of the equivariant kernels by putting an element of the canonical basis this point and summing element. More precisely, we impose having some matrix Ki at the point x * 0 and to obtain the full equivariant kernel, we just apply the following formula:
the group G the action of an element of G on this
Vy R
b(y) = KPgg (v)
Σ gEG
(27)
This formula is well defined because in the of subgroups of 0()), Vz, y (0), the set {g E G.g - x = y) is finite meaning that the above sum is finite for every E R2. remains to check that the kernel KP respects the above condition on equivariant kernels. Indeed, one has that:
Vy E V.
(h. v) = Σ K5 (h.,)))((o=")))
G.
gEG
Σ
Pi+ p4+1())pi1100 (B)))))) (1)))))))))))
gEG
= Ph- P K)
9)) -)))))))) ((
p((h)-)
9EG
= -p- (2)
where we used that + h-19 g from G to G is bijection. One should note that for some groups G and some x o it may be possible that 3g E G, g- -- x. The set all elements that keep the point unchanged is known the stabilizer subgroup. For example, for G dihedral group and a point x on the symmetry axis, one has that x remains untouched by the symmetry with respect to this axis. This is however not problem. formula is still valid, even at the point x. One will note however that kP.9 (x) o K (z). This means that we may lose the fact that the set of equivariant kernels (K G.z: (p. q) E [cin] x [Coun] is composed of independent vectors and therefore forms a basis. We will still have that spans the space of equivariant kernels but not that will form basis.
the set of such g is finite. and therefore the above
23

---

Published as a conference paper at ICLR 2023
E.2 CONSTRUCTION OF THE KERNEL AT THE ORIGIN
We would like to apply our basis construction formula to every point in the plane, including the origin but the problem that at the origin: Vg E G, 9-0 O. Therefore the above sum is not well defined because it is infinite for infinite groups. We can only apply this formula in the case of G finite. The usual way to solve the problem at the origin if one deals with infinite groups to solve all the linear problems π (g z) Poor (g)((g) (m)) (g) However in the setting of Corollary 3, we deal with finite subgroups of (22). Therefore we can apply the above formula:
Vy E R² b(y)
KPgg (w) = Σ Eeti (o) "0)0)))))) ")) G.0
gEG
In our case, when dealing with the regular representation, if one takes G = C. the cyclic group of rotations, one will check that the (((g) are permutation matrices associated with the permutation of G': h + g h. One can then check that summing over G leads to a circulant matrix.
We have thus computed the set of equivariant kernels at the origin by using the above formula. One may have wanted to solve all the linear problems set by the equivariant constraints. Here they can be reformulated by the fact that the kernel at the origin must commute with all the matrices associated with the permutations of G h + g h. Solving this leads to the set of circulant matrices.
E.3 DISCRETIZATION OF R
We now highlight the practical challenges of building equivariant networks and their associated pruning when we discretize continuous signals on R² to a pixelized grid.
From 2 to 1 - The first problem we want to address is that we do not usually work on the plane R2 but on spatially delimited images 1- d'2 This is prohlematic since when G acts square images, it can become a non-square image after a rotation. For example, C3 doe not always send 1- d 212 on [-2- 2'2
d11 (take the rotation by 45 for instance). In the same way restricting the equivariant kernel to a finite space [- d-2
2222 2 as it is done in usual CNNs would lead to problems since d d.2. We overcome this issue by restricting the 2' 2:2
for some |- 2 d/ and some g G. g- [ kernels to not being defined B² but size of the image (see Figure 2). To implement this, we multiply with a mask which exponentially decays zero for points with radius larger than the radius of the disk. This is permitted because the equivariant constraint set constrains the interior of the orbit, and is trivial that for sub-groups of O22), the disc is stable under the action of the group. Therefore, the kernels that we obtain are still equivariant because they can check the equivariant constraint.
disk centered at the origin whose diameter equals the
From - 2 {-1 - d-2 ..... 22 2 32. The second problem that we must address is the __,,..,
discretization process. Indeed, we do not work with continuous feature fields f [- - 4 + R but with pixellized images, i.c. discretized inputs f - ...., 2 - R. This problem, because the equivariant constraint Eq. 26 puts constraints between k(g x) and k(x). Equation 26 cannot be used anymore because g not always on the grid. For instance, if = (1, 1) and g Moreover, note that it is not sufficient to discretize the equivariant kernels: one must choose only finite subset of them. Indeed, the dimension of the equivariant map must be finite in the discretized setting as opposed to the continuous setting where it is infinite. In practice, the network is not exactly equivariant, but almost equivariant due to a discretization error. However, this is not an issue the setting of Theorem 1. Indeed, once we have chosen a basis of the allmos-equivarian the class of such networks, which exactly the result that we want in practice.
the rotation by 45,, then g x = (0, 22) & {-2. d=2 -
1)2 _
.....
kernels, we can prove the SLTH for
Weiler and Cesa (2019) choose a finite subset of the equivariant kernels, the authors upper-bound the frequency of the polar coordinate solution by an anti- anti-aliasing condition. They then discretize the continuous kernels on the grid. For our basis construction, we choose finite subset of the equivariant kernels by restricting Ar to only Ar -
2: d-2 ..... 2)2. There are many different ways to discretize our kernels KP:2 defined on IR.2 One way would be to send g x to the nearest pixel it is not on the grid. In order to decrease the discretization error, we first upsample the grid by factor 3 before we start applying actions of the group G to the base space. For the subgroups of
24

---

Published as a conference paper at ICLR 2023
(2) consider, rotations of the base space are performed using bilinear interpolation. Finally, downsample to the original size in order to obtain the discretized version of K
E.4 PROOF SLT ON STEERABBEE CNNS USING THEOREM
We now prove Corollary 1. We work with trivial or regular representations of G < ((2) on top of feature fields. It is straightforward that the pointwise ReLU equivariant. Moreover, easily compute [+|||| we work with || oloo which implies that the ReLU is then 1-Lipschitz. Finally, the identity can trivially be written as the convolution with an equivariant kernel having the identity at the origin (the identity is trivially a circulant matrix). Therefore we have that 1 E B
top of the feature field layer then the building block of this layer is FF Rd² If we instead use a regular representation, then the building block of this layer is F, = <x(x From the construction of the equivariant basis, we deduce that [B++41| < d G|2 for each layer. Indeed, we must first choose pixel on the set of representatives AR C( d. d-2 ..... d-2 d 2) [d] [d] grid, and then choose subset of the canonical basis at this point. But such canonical basis has |G] x |G' elements for regular to regular, x |G' element for trivial to regular (or regular to trivial). and finally only 1 for trivial to trivial. This even less than that at some points such as the origin because of the additional constraints. Finally, one has less that d² | choices in all cases which indicates that,
If we use trivial representation
[L4+1| dIG??
In fact, since we can only choose x E AR to obtain a set of independent elements, the true dependency will be |Br++1|| |AR |G|2 [ল |G|2 d!GG). However because of the discretization procedure, is easier to upper bound by d² G/2 since the cardinal of the discretized version of Ag is not casily computable. Moreover, the reader will note that the cardinal of the basis has no real significance by itself because the basis was computed with an arbitrary discretization procedure, and therefore another procedure may have lead another cardinal. Due to the artifacts during the discretization procedure the basis we construct Bi-i41 and only approximate a subset of all equivariant maps. We compute [| II when employing the lloc each feature space. Applying the triangular inequality we get:
d
B S |B
max
|| b+
b2 LELLAE
It remains then to upper-bound [|0;= IIl for every element in the basis. For all x E AR and for all p. q E [[G]] denote bi-r441.p...z the convolution with the equivariant kernel G We have using a result from da Cunha et al. (2022b) that || < K Then, in non-discretized kernel setting, while noticing that the orbit of x has G elements, one has || S |G]. Then,
llbb-ii+...... IIl I |G]. For the identity this remains true as by using of circulant matrices it is trivial 2. G.0 = |G].
that [
F ADDITIONAL MATERIAL ON THE PERMUTATION EQUIVARIANT NETWORKS
F.1 PROOF OF SLT ON PERMUTATION EQUIVARIANT NETWORKS
The aim of this appendix is to prove Corollary 2. The building blocks of the layers are here F, = n** Taking direct sums of them we obtain F. R xn. Again as in appendix section E.4, the pointwise ReLU equivariant and furthermore we facilitate the computation of || IIl by working with ||- Iloo. which implies that the ReLU is 1-Lipschitz. As explained above, the norm that we must consider on FT; Ra* xn; to apply theorem is the max of the norm across the blocks, i.e. still
||- bl on In" xn. First, observe that || 8 + 1.
Proof. One can check that the worse case scenario happens when making EbgeB by act on a tensor X E R full of 1. Denote by Y, for a E [m]]k: the tensor in Ra such that has a at the index and 0 everywhere else. The tensor full of 1 is therefore Eaejaj Y.
25

---

prune an overparameterized Published as a conference paper at ICLR 2023
|B,+++
max
max ||]| S
Σ Ore
X
|| 1
bk
Σ Y
buEB
aE(nn)
1+
B
Ye
20
max
Σ
B"
Σ Ya
[--1
12
aEjn)a
Now, Vb [n]
Σ Ya ))
((T
Σ
B"
=1
E
B"
Ya
WE(n/MetRct1// /Q
aE[ni"
aE|ns**
= =1
Σ
Bla.biy
b
1
Σ
aE(n]*
1 + n hi
Moreover |B--++1| bkks (11k++-44p) k241) by definition of the Bell numbers. In fact the interested reader will check that one has B < b(k)++k+11) and that the equality happens example with n 1 one can not have an independent vector family of b(k;++ vectors in C(R. R) which is of dimension 1. The argument expressed in Maron et al. (2019) needs n 2 k; + +++1 to ensure that all the equivalence classes f have least one element. Finally, all the conditions apply theorem B,+++ III) by max(b(k; + ki+1), n + 1).
k2 ke+1 (for
1 are true and one only need to replace
G EXPERIMENTAL DETAILS
The purpose of our experiments is to empirically validate the our theory found in the main text, and as result show that by solving appropriate SUBSET-SUM problems random network to a target one. In this section of the appendix, we describe the network architectures use for experiments, the overparamettriizatio scheme select in order be compatible with our claims, and the linear program we solve for each target weight in order to find the sparsification mask which leads the approximation of the target network by the overparameterized
For both MPGNN and E(2)-CNN experiments, we first train a single target network on the supervised tasks that described in table 3. The architecture in the tables 4, 5, and below. Notice that we do not utilize bias the parameterized layers, as well we do not make of learnable element-wise affine transformations in the batch normalization layers. We train for 50 epochs using Adam as the optimizer with learning rate 0.015 and default momentum parameters 8 = (0.9, 0.999) and cosine scheduler. The weight decay coefficient is set to 5e-4. 4. For the transductive learning tasks on Cora and CiteSeer with the MPGNN, we define an epoch as 10 parameter updates. For the image classification tasks RotMNIST and FINPRO
for each of the target networks is described
26

---

Published as a conference paper at ICLR 2023
with the B(2)-CNN the batch size is set 64. Finally, the target model is selected as the which achieves the best validation accuracy throughout training.
Afterwards, we define the overparameterized network. In particular, for each parameterized layer (linear or equivariant) of the target network we declare a module that we are going to approximate with. The module consists of the composition of three layers, the first and the last being of the same lype as the target layer, and the middle one is an element-wise ReLU activation function. We make source that the shapes of the input and output tensors match. We initialize these modules using iid drawn samples from U[[aa a)). where a is determined as twice the maximum absolute parameter of the target network. As we explain in the appendix section A, this is compatible with our theorem.
For each parameter in the target network we solve two SUBSET-SUM problems, one to approximate the positive input tensors and one to approximate the negative input tensors. This distinction is needed we want to use a ReLU in the overparameterized layers. The width overparameterized by multiplying the input tensor size with number that scales proportionally constant factor C, and logarithmically in the input and output size, the number of layers to be approximated, and in 1/e, where is the desired network approximation error. For our experiments, we use le-2. For further details, the reader is requested to examine the associated Python repository that we provide.
hyperparameter
Finally, we solve each defined SUBSET-Sta problem by treating it as a mixed-integer linear program, similarte to Pensia et al. (2020). Each one of the problems amounts to different constraint optimization problem of the following form:
min mEZg
(28)
s.t. 2 m T x <=
m T x <=
In the optimization problem above, æ is a vector resulting from the multiplication of the two weight matrices which participate in the diamond-shaped approximation scheme for each target weight as explained in Optimization variables = and m amount to the absolute weight approximation error and part of the binary mask of the second layer in the overparameterized network, which is responsible for approximating the particular weight y.
Layer
Pin
Pout
GCNConv ReLU & Dropout(prob. = 0.5)
data features
16
GCNConv
16
16
ReI.U & Dropout(prob. = 0.5)
GCNConv
16
number of classes
Table 4: Target network architecture for the MPGNN experiments.
Layer
Pin
Pout
R2Conv(kernel = 9))
number channels x trivial repr.
24 regular repr.
InnerBatchNorm
Pointwise Max Pool(kerncl = (2, 2))
Pointwise ReLU
R2Conv(kernel=77,7)
24 regular repr.
48 regular repr.
InnerBatchNorm
Pointwise ReLU
GroupPooling
Max Pool(kernel = (2, 2)) & Flatten
Linear
48 |G]
48
BatchNorm & ReLU
Linear
48
number of classes
Table 5: Target network architecture for the E2CNN experiments.
27

---

Published as a conference paper at ICLR 2023
Layer
Pin
Pout
Linear 2 +
data features x.V2
16 x N
Linear 2 ++
16 N2
32 N
Sum Pooling across N & Flatten Linear ReLU
32
64
Linear
64
number of classes
Linear 2 ++ ReLU
data features xN2
24 x N²
Linear 2 ++ 2 ReLU
24 x N2
48 x N
Linear 2 +
48 N22
96 N
Sum Pooling across & Flatten
Linear ReLU
96
96
Linear
96
number of classes
Table 6: Target network architecture for the k-order -quuiiiirr GNN experiments. Top architec- ture was used for the Proteins dataset, whereas the bottom one for the NCI1 dataset.
28


Reviews:
[{"review_id": "gW_6h2cxtl", "reviewer": "Reviewer_THqA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a framework for proving the Strong Lottery Tickey Hypothesis (SLTH) for G-equivariant networks based on the proof by Pensia et al. They show that within this framework, several of the known results (Pensia et al., da Cunha et al., Burkholz et al.) can be considered instantiations of the general theorem.", "summary_of_the_review": "I think the paper is a reasonable contribution. I have some questions and clarifications but if those are answered, I would recommend acceptance.", "strength_and_weaknesses": "**Strengths:**\n1. The paper seems to be technically sound and a generalization of several known Strong LTH results. I am not yet convinced that Equivariance is an important property of DNNs but it seems that there is some interest in the area.\n2. The paper is fairly well written with few typos which I will point out.\n\n**Weaknesses:** (I will also include my questions for clarification here)\n1. In the end of section 2 it is stated \"With no assumption on the inputs, ...\" - I don't follow this statement. Can you elaborate?\n    - Also, merely a few paragraphs later, the inputs are assumed to be bounded in the unit $\\ell_2$ sphere and the same decomposition is invoked. So I don't follow the criticism of Pensia et al. here.\n\n2. Minor typos:\n    - In Section 3.1, \"To approximates $f$...\" is a typo.\n    - In Section 3.2, \"is far from optimal as their result give guarantees..\" is a typo.\n    - In Section 4.2 and a few other places, the $\\times$ operator seems to be typeset incorrectly. Please check.\n    - Please use \\citep{} when citing multiple works in the end of a sentence.\n\n3. End of Section 3.1 states that this result improves on the overparameterization of Pensia et al., since G-equivariant networks have fewer effective parameters.\n    - However, Pensia et al., prove a result about pruning an overparameterized dense network to recover a dense target network while the result here is to approximate  G-equiariant net. Does this result give a tighter bound even when approximate dense networks? Otherwise, the comparison is incorrect and unfair.\n\n4. Section 3.2 states that the lwoer bound is (tight)\n    - This is untrue. The bound is loose by a $\\log(n)$ factor which they claim can be culled since it arose from a poor choice norm. However, in the appendix they say that a rescaling \"might\" eliminate the term.\n    - It is also stated that by choosing the weights carefully, it can be eliminated. But the randomness is essential for the definition of a Strong LT. Also, if one is allowed to choose the weights exactly, you could choose a bespoke overparamterization for each target network which makes the entire result useless.\n    - I'm still not convinced that the $\\log(n)$ term is easy to get rid of.\n\n5. In Section 1, it is stated that \"Moreover, Theorem 1 can be extended to the settings where overparamatrized networks have depth $L+1$ as in Burkholz (2022b)\"\n    - However, all the results in the paper seemed to need $2L$ depth. Can you point me where this is shown?\n\n6. Table 3 results:\n    - The overparameterization required in the results seems to be extremely high. The experiments are in-line with Pensia et al., but the overparameterization there seemed to be more like $10$. Also, in Ramanujan et al., the required overparmaterization is $2$ or $4$. Is there a reason the overparamterization is so large here?\n\n7. Lemma 3 in Appendix:\n    - It is stated that these results are extensions of those specified in Pensia et al. I believe this result is stated as a remark in Pensia et al. Please check.\n\n8. Appendix B.3: Lower bound:\n    - I don't understand several of the statements following Theorem 2. It is stated that the assumptions are \"only used to ensure that the lower bound holds\" - I'm not sure how this is a valid justification of the assumption. It seems fairly essential to the proof.\n    - I agree that the assumptions are mild and have no problem with their usage, but these statements are somewhat misleading.\n\n9. Table 4 and Table 5 are very hard to read. Please clean them up.\n\n10. Similarity to Pensia et al.:\n    - The proof techniques, statements and even the lower bound seem almost identical to Pensia et al. with a switch in terminology to account for equivariant networks.\n    - While I don't question that this is a valid contribution, I can't help but feel there is a simpler way to transfer these proofs to this domain.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R0Gg9vz3CH1", "reviewer": "Reviewer_Tcgp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work introduces a unifying framework to prove the strong lottery ticket hypothesis for general equivariant networks. Firstly, the authors prove that any fixed width and depth G-equivariant network that uses a point-wise ReLU activation function can be approximated with high probability to a pre-specified tolerance by pruning a randomly initialized overparameterized G-equivariant network to a G-equivariant subnetwork. Additionally, this work proves such a prescribed overparametrization scheme is optimal and provides a corresponding lower bound. Experiments on E(2)-steerable CNNs, k-order GNNs, and MPGNNs validate the proposed theory.", "summary_of_the_review": "None", "strength_and_weaknesses": "### Strength:\n\n1. This work proposes a theoretical justification of the strong lottery ticket hypothesis for general equivariant networks.\n2. This paper is well-organized, starts from the theoretical results of general equivariant networks, and follows by specific case studies as well as empirical evidence.\n3. Experiments are conducted across several equivariant networks. \n\n### Weakness:\n\n1. Whether the proposed framework can further be extended to equivariant networks with other activation functions besides point-wise ReLU?\n2. Minor: The y-axis is covered by other subfigures in Figure 3.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PwP9VXJniO", "reviewer": "Reviewer_g7iD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Recent work has shown that the strong lottery ticket hypothesis (SLTH) can be extended to classical convolutional neural networks, with a similar level of overparameterization as for dense networks. CNNs are translation equivariant (ignoring pooling and edge effects), so a natural question to ask if the SLTH can be extended to more general G-equivariant networks. The main contribution of this paper is to show SLTH can indeed be generalized to G-equivariant networks. \n\nThe question whether there should exist equivariant strong lottery tickets for sufficiently overparatermized G-equivariant NNs is not trivial at first, but in hindisight fairly obvious (as explained below). The lack of triviality partly stems from the fact that the sub-network extraction can easily result in loss of equivariance, defeating the purpose. Nonetheless, the authors show that this is possible i.e. a target GCNN with fixed width and depth (and which uses a pointwise non-linearity like the ReLU) can be approximated with high probability by a subnetwork in a random GCNN which has double the depth, and has the width increased by a log factor. This subsumes results of Pensia et al. and Orseau et al. for MLPs and that of Bukrholz et al. and da Cunha et al. for CNNs. The authors also show that a log factor increase in width is actually optimal, and this work irrespective of the overparameterization strategy employed. \n\nThe authors rely on the use of a G-equivariant basis -- which is a basis of equivariant linear maps between two vector spaces. The error metric the authors consider (for the approximation quality of the subnetwork) is uniform approximation over a unit ball. The approaches of Pensia et al. da Cunha et al., Burkholz et al. are adapted to work for the equivariant case. More specifically, the subset sum approach fails if applied as is. The idea for pruning then becomes pruning out the weights that combine the equivariant basis (rather than pruning in a canonical basis as parameters of the weight matrices can't be directly pruned). Thus what might seem non-trivial at first is fairly obvious -- we simply need to prune the parameters that combine elements of this basis. However, this introduces an additional difficulty of dealing with pointwise non-linearities like ReLU effectively -- which is an additional technical challenge that the authors address.\n\nFinally, the authors present case studies for specific choices for G. For the translation group their results generalize earlier results. The main theorem is also applied for the E(2) steerable case, permutation equivariant networks, and message passing networks. Experimental results show that the proposed approach is able to approximate the target network adequately. ", "summary_of_the_review": "See above.", "strength_and_weaknesses": "- The problem is well-motivated and important. G-equivariant networks are now becoming increasingly important in applications, especially in the physical sciences. It is thus important to understand if an equivalent of the strong lottery ticket hypothesis also holds for them. \n- The results are solid to the best of my knowledge (although I have only worked through the proofs while skipping some details). The approach is fairly obvious -- they adapt earlier work, but not to prune the weights themselves, but the coefficients that are used to combine the equivariant bases. \n- The case-studies for the 4 cases considered are useful to position the results in context. \n- The results generalize earlier results for MLPs and CNNs. \n- Experimental resuls show a proof of concept that their approach is able to find such sub-networks. \n- Paper is well-written and is easy to follow. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "6uYBf4Sr3_", "reviewer": "Reviewer_3WVk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves the Strong Lottery Ticket Hypothesis (SLTH) in the context of equivariant neural networks. The SLTH states that for every network f, and every sufficiently overparametrized, randomly-initialized network h, there is a pruning of h that recovers f.\n\nPrior work: In the context of fully-connected networks, the SLTH was proved by Malach et al.’20 and then strengthened by Pensia et al.’20, who gave upper and lower bounds.\nThe SLTH was extended to CNNs by da Cunha et al.’22 and Burkholz ’22, where the key new technical contribution was to give a pruning scheme that preserved translation equivariance of the network.\n\nThis work: This work generalizes the arguments of Pensia et al’20 and Burkholz’22 to apply to any equivariant networks. The pruning scheme bears similarity to Pensia et al.’20, but with the main difference that it works by pruning weights in an equivariant basis.\nThe main theorem proving SLTH is discussed in the contexts of E(2)-steerable networks and permutation equivariant networks, and experiments are given to verify its validity.\n", "summary_of_the_review": "This paper is well-written and unifies and generalizes previous results on Strong Lottery Ticket Hypothesis for MLPs and CNNs. I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n* The SLTH is of great interest to the community, and this papers’ results seem to nicely generalize all previous papers, in particular recovering the result for CNN.\n* The construction is neat and easy to follow.\n\nWeaknesses:\n* The setting of SLTH is not novel, and has been previously studied. The proof techniques in this paper are also quite similar to the proof techniques of previous papers, but generalized to equivariant networks in general (beyond MLPs and CNNs). Nevertheless, I understand that this is not an actionable criticism for the authors.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster