Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?
Authors: Matthew Farrell
Blake Bordelon
Shubhendu Trivedi
Cengiz Pehlevan
Venue: ICLR 2022 Poster (2022)
Keywords: representation learning
perceptron capacity
perceptual manifolds
equivariance
cover's theorem
vc dimension

Abstract: Equivariance has emerged as a desirable property of representations of objects subject to identity-preserving transformations that constitute a group, such as translations and rotations. However, the expressivity of a representation constrained by group equivariance is still not fully understood. We address this gap by providing a generalization of Cover's Function Counting Theorem that quantifies the number of linearly separable and group-invariant binary dichotomies that can be assigned to equivariant representations of objects. We find that the fraction of separable dichotomies is determined by the dimension of the space that is fixed by the group action. We show how this relation extends to operations such as convolutions, element-wise nonlinearities, and global and local pooling. While other operations do not change the fraction of separable dichotomies, local pooling decreases the fraction, despite being a highly nonlinear operation. Finally, we test our theory on intermediate representations of randomly initialized and fully trained convolutional neural networks and find perfect agreement.

Published as a conference paper at ICLR 2022
CAPACITY OF GROUP-INVARIANT LINEAR READOUTS FROM EQUIVARIANT REPRESENTATIONS: How MANY OBJECTS CAN BE LINEARLY CLASSIFIED UNDER ALL POSSIBLE VIEWS?
Matthew Farrell':, Blake Bordelon" Shubhendu Trivedi', & Cengiz Pehlevan
Harvard University
{ms farreel, blake bordelon, cpehlevan]Jseas hww.aaaadd.aa..aaad..o.omm harvard.
Massachusetts Institute of Technology shubhenduccsal/ ienaiiiliiittt... eddu
ABSTRACT
Equivariance has emerged as desirable property of representations of objects subject to translations and rotations. However, the expressivity of representation con- strained by group equivariance is still not fully understood. We address this gap by providing a generalization of Cover's Function Counting Theorem that quanti- fies the number of linearly separable and group-invariant binary dichotomics that can be assigned to equivariant representations objects. We find that the frac- tion of separable dichotomies is determined by the dimension of the space that is fixed by the group action. We show how this relation extends to operations such convolutions, element-wise nonlinearities, and global and local pooling. While other operations do not change the fraction of separable dichotomies, local pool- ing decreases the fraction, despite being a highly nonlinear operation. Finally, we test our theory on intermediate representations of randomly initialized and fully trained convolutional neural networks and find perfect agreement.
transformations that constitute a group, such as
INTRODUCTION
The ability to robustly categorize objects under conditions and transformations that preserve the object categories is essential to animal intelligence, and to pursuits of practical importance such as improving computer vision systems. However, for general-purpose understanding and geometric reasoning, invariant representations of these objects in sensory processing circuits are not enough. Perceptual representations must also accurately encode their transformation properties.
One such property is that of exhibiting equivariance to transformations of the object. When such transformations restricted to be an algebraic group, the resulting equivariant representations have found significant success in machine learning starting with classical convolutional neural networks (CNNs) (Denker al.. 1989; LeCun al., 1989) and recently being generalized by the influen- tial work of Cohen & Welling (2016). Such representations have elicited burgeoning interest as they capture many transformations of practical interest such as translations, permutations, rotations, and reflections. Furthermore, equivariance to these transformations can be easily "hard-coded" into neural networks. Indeed, a new breed of CNN architectures that explicitly account for such transfor- mations seeing diverse and rapidly growing applications (Townshend et al., 2021; Back et al., 2021: Satorras et al., 2021; Anderson et al., 2019: Bogatskiy et al., 2020; Klicpera et al., 2020; Winkels & Cohen, 2019; Gordon et al., 2020; Sosnovik et al., 2021; Eismann et al., 2020). In ad- dition, equivariant CNNs have been shown to capture response properties of neurons in the primary visual cortex beyond classical Gábor filter models (Bcker et al., 2018).
"These authors contributed equally.

---

Published as a conference paper at ICLR 2022
While it is clear that equivariance imposes strong constraint the geometry of representations and thus of perceptual manifolds (Seung & Lee, 2000; DiCarlo & Cox. 2007) that are carved out by these representations
the objects transform, the implications of such constraints are not well understood. In this work we take a step towards addressing this gap. Our starting point is the classical notion of the perceptron capacity (sometimes also known the fractional memory/storage capacity) a quantity fundamental to the task of object categorization and closely related to VC dimension (Vapnik & Chervonenkis, 1968). Defined as the maximum number of points for which all (or 1-5 fraction of) possible binary label assignments (i.e. dichotomies) afford a hyperplane that separates points with one label from the points with the other, it can be seen to offer a quantification of the expressivity of a representation.
their expressivity
Classical work on perceptron capacity focused on points general position (Wendel, 1962; Cover, 1965; Schläfli, 1950; Gardner, 1987; 1988). However, understanding the perceptron capacity when the inputs are not merely points, but are endowed with richer structure, has only recently started to attract attention. For instance, work by Chung et al. (2018); Pastore et al. (2020); Rotondo et al. (2020); Cohen et al. (2020) considered general perceptual manifolds and examined the role of their geometry to obtain extensions to the perceptron capacity results. However, such work crucially relied on the assumption that each manifold is oriented randomly, a condition which is strongly violated by equivariant representations.
With these motivations, our particular contributions in this paper are the following:
We extend Cover's function counting theorem and VC dimension to equivariant representations, finding that both scale with the dimension of the subspace fixed by the group action.
We demonstrate the applicability of our result to G-convolutional network layers, including pool- ing layers, through theory and verify through simulation.
1.1 RELATED WORKS
Work most related to ours falls along two major axes. The first follows the classical perceptron capacity result on the linear separability of points (Schläfli, 1950; Wendel, 1962: Cover, 1965; Gardner, 1987; 1988). This result initiated long history of investigation in theoretical neuroscience, e.g. (Brunel et al., 2004; Chapeton et al., 2012: Rigotti et al., 2013; Brunel, 2016; Rubin et al., 2017; Pehlevan & Sengupta, 2017), where is used to understand the memory capacity of neuronal architectures. Similarly, in machine learning, the perceptron capacity and its variants, including notions for multilayer perceptrons, have been fundamental to a fruitful line of study in the context of finite sample expressivity and generalization (Baum. 1988; Kowalczyk, 1997; Sontag, 1997; Huang, 2003: Yun al.. 2019: Vershynin, 2020). Work closest in spirit to ours comes from theoretical neuroscience and statistical physics (Chung et al., 2018; Pastore et al., 2020; Rotondo et al., 2020; Cohen et al., 2020), which considered general perceptual manifolds, albeit oriented randomly, and examined the role of their geometry to obtain extensions to the perceptron capacity result.
The second line of relevant literature is that on group-equivariant convolutional neural networks (GCNNs). The main inspiration for such networks comes from the spectacular success of classical CNNs (LeCun et al., 1989) which directly built in translational symmetry into the network architec- ture. In particular, the internal representations of CNN approximately translation equivariant: if the input image is translated by an amount 4, the feature map of each internal layer is translated by the same amount. Furthermore, an invariant read-out on top ensures that a CNN is translation invariant. Cohen & Welling (2016) observed that a viable approach to generalize CNNs to other data types could involve considering cquivariance more general transformation groups. This idea has been used to construct networks equivariant to a wide variety of transformations such as pla- nar rotations (Worrall et al., 2017: Weiler et al., 2018b; Bekkers et al., 2018; Veeling et al., 2018; Smets et al., 2020), 3D rotations (Cohen et al., 2018; Esteves et al., 2018; Worrall & Brostow, 2018;
Weiler et al., 201 Sa;; Kondor et al., 201 2018a; Perraudin et al., 2019), permutations (Zaheer et al., 2017:
Hartford et al., 2018: Kondor et al., 2018b; Maron et al., 2019a; 2020), general Euclidean isome-
tries (Weiler et al., 2018 3018a; Weiler & Cesa, 2019; Finzi et al., 2020), scaling (Marcos et al., 2018:
Worrall & Welling, 2019; Sosnovik et al., 2020) and more exotic symmetries (Bogatskiy et al., 2020;
Shutty& & Wierzynski, 2020; Finzi et al., 2021) etc.
'ooee operations such as max pooling and boundary effects of the convolutions technically break striet cquivariance, as well the final densely connected layers.
2

---

For concreteness, one might imagine that each of the rd is the neural representation for an image of a dog (if yd = +1) or of a cat (if y -). The action T(g) could, for instance, correspond to the image shifting to the left or right, where the size of the shift is given by g. Different representations Published as a conference paper at ICLR 2022
A quite general theory of equivariant/nvvaiint networks has also emerged. Kondor & Trivedi (2018) gave a complete description of GCNNs for scalar fields on homogeneous spaces of compact groups. This generalized further to cover the steerable case in (Cohen et al., 2019b) and to general gauge fields in (Cohen et al., 201 9a; Weiler et al., 2021). This theory also includes universal approxima- tion results (Yarotsky, 2018; Keriven & Peyré, 2019; Sannai et al., 2019h; Maron et al., 2019b; Segol & Lipman, 2020; Ravanbakhsh, 2020). Nevertheless, while benefits of equivariance/invarincc in terms of improved sample complexity and ease of training are quoted frequently, a firm theoretical understanding is still largely missing, Some results however do exist, going back to (Shawe- Taylor, 1991). Abo-Mostafa (1993) made the argument that restricting a classifier be invariant can not increase its VC dimension. Sokolic et al. (2017) extend this idea to derive generalization bounds for invariant classifiers, while Sannai al. (2019a) do so specifically working with the permutation group. Flesedy & 7aidi (2021) show a strict generalization benefit for equívariant linear models, showing that the gencralization gap between a least squares model and its cquivariant version de- pends the dimension of the space of myti-yymmetiic linear maps. Some benefits of related ideas such as data augmentation and invariant averaging are formally shown in (Lyle et al., 2020; Chen et al., 2020). Here we focus the limits to expressivity enforced by equivariance.
PROBLEM FORMULATION
Suppose abstractly represents an object and let rax) E T be some feature map of æ to an N N-dimensional space (such as an intermediate layer of a deep neural network). We consider trans- formations of this object, such that they form a group in the algebraic sense of the word. We denote the abstract transformation of x by element E G as gæ. Groups G may be represented by invert- ible matrices, which act vector space V (which themselves form the group GL(V) of invertible linear transformations on V). We are interested in feature maps r which satisfy the following group equivariance condition:
r(gæ) = (g)r(x)),
where G - G is linear representation of G which acts feature map r(x). Note that many representations of G are possible, including the trivial representation: [gg) = for all g-
We are interested in perceptual object manifolds generated by the actions of G. Each of the P manifolds can be written as a set of points {T())"" g E G} where E [P] = f1,2...., P): that is, these manifolds are orbits of the point pe rr(* under the action of We will refer such manifolds as 7-manifolds.?
Each of these m-manifolds represents single object under the transformation encoded by π: hence, each of the points in a m-manifold is assigned the same class label. A perceptron endowed with a set of linear readout weights w will attempt determine the correct class of every point in every manifold. The condition for realizing (i.e. linearly separating) the dichotomy {8r) }j, can be written as y"w (r) > 0 for all E G and f E [P], where y" +1 if the 11th manifold belongs to the first class and y" = -1 the nT manifold belongs to the second class. The perceptron capacity is the fraction of dichotomies that can be linearly separated; that is, separated by hyperplane.
of even the same group can have different coding properties, an important point for investigating biological circuits and one that we leverage to construct a new GCNN architecture Section 5.
3 PERCEPTRON CAPACITY OF GROUP-GENERATED MANIFOLDS
Here we first state and prove our results in the general case of representations of compact groups over R.N. The reader is encouraged to read the proofs, as they are relatively simple and provide valuable intuition. We consider applications to specific group representations and GCNNs in Sections 4 and 5 that follow.
Note that for finite group G. each manifold will consist of a finite set of points. This violates the technical mathematical definition of "manifold", but we abuse the definition here for the sake of consistency with related work (Chung et al., 2018; Cohen et al., 2019h); to be more mathematically precise, one could instead refer to these "manifolds" as orbits..
3

---

Published as a conference paper at ICLR 2022
3.1 SEPARABILITY OF T-MANIFOLDS
We begin with a lemma which states that classifying the r-manifolds can be reduced to the problem of classifying their P centroids. For the rest of Section 3, we let G + GL(RR) be an arbitrary linear representation of a compact group G. We denote the average of x over with respect to the Haar measure by (g()))EC for finite G' this is simply T Egec (gg) where |G] is the
order (i.e. number of elements) of G. For ease of notation we will generally write (x) = (x (G) when the group G being averaged over is clear.
(e,, consisting of P T-manifolds with labels y is lin- early separable if and only if the dataset {((T)r", JEEPP consisting of the P centroids (r)r" with the same labels is linearly separable. Formally,
Lemma 1. A dataset (g(g))" y²))
Eu Vg E G. I. E [P] yu =())r" >0 = Eo V/ E [P]: y"w (T) > 0.
Proof. The forward implication is obvious: if there exists a w which linearly separates the P mani- folds according an assignment labels y", that same w must necessarily separate the centroids of these manifolds. This can be seen by averaging each of the quantities y"w (g)r"" over g E G. Since each of these quantities positive, the average must be positive.
w. For the reverse implication, suppose yow" (TT) > 0, and define v (T) Tw. We will show that w separates the P π -a-mooold since
ÿ (g)r y"w (T))(())r" (Definition of w))
= y"w (T(g') (m(g))m())) (Definition of (अ) and linearity of π (gg)
= y w (T))** (Invariance of the Haar Measure ((Sy) = (uS) for set S)
> 0 (Assumption that w separates centroids)
Thus, all that is required to show that w separates the T-orbits are basic properties of group representation and invariance of the Haar measure to G-transforrations.
3.2 RELATIONSHIP WITH COVER'S THEOREM AND VC DIMENSION The fraction f of linearly separable dichotomies on a dataset of size P for datapoints in general position in N dimensions was computed by Cover (1965) and takes the form
N-1 Σ
[(P,N)= 2
(I)
k
where we take (m) = for m > n. Taking a = P/N, f is a nonincreasing sigmoidal func- 2, and approaches 0 a + co. In the thermodynamic limit of P, P - 00 and a = 0(1), f(a) converges to a step function f(a) Nimp,N--oe,:= a=/NN [(P N) O(2 a) (Gardner, 1987; 1988; Shcherbina & Tirozzi, 2003), indicating that in this limit all dichotomies are realized if a < 2 and no dichotomies can be realized if a 2, making a a critical point in this limit.
tion of a that takes the value when
1/2 when
The VC dimension ( (Vapnik & Chervonenkis, 1968) of the perceptron trained on points in dimension N defined to be the largest number of points P such that all dichotomies are linearly separable for some choice of the P points. These points can be taken to be in general position. Because [(P, N) = precisely when P < N, the VC dimension is always N = P for any finite N and P (see Abu-Mostafa et al. (2012)), even while the asymptotics of reveal that [(P, N) approaches 1 at any N > P/2 as N becomes large. In this sense the perceptron capacity yields strictly more information than the VC dimension, and becomes comparatively more descriptive of the expressivity as N becomes large.
In our G-invariant storage problem, the relevant scale is P/No where No is the dimension of the fixed point subspace (defined below). We are now ready to state and prove our main theorem.
Note that our results extend to more general vector spaces than N under condition that the group be semi-simple.
"A set of P points is in general position in N --space if every subset of N fewer points is linearly independent. This says that the points are "generic" in the sense that there aren't 't any preserihed special linear relationships between them beyond lying in an N-dimensional space. Points drawn from a Gaussian distribution with full-rank covariance are in general position with probability one. "Tiis is because linear dependeneies decrease the number of separable dichotomies (sce Hertz et al. (2018)).
4

---

Published as a conference paper at ICLR 2022
Theorem 1. Suppose the points (I)r" for μ E [P] lie in general position in the subspace Vo range (m)) = {T)) : x E V]. Then Vo is the fixed point subspace of n. and the fraction of linearly separable dichotomies on the P TT-anifolds {π(g)r" g & G} is f(P, where No dim Vo- Equivalently, No is the number of trivial irreducible representations that appear in the decomposition of into irreducible representations.
The fixed point subspace is the subspace W fw E Vlgw .Vg E G). The theorem and its proof use the notion of irreducible representations (irreps), which are in essence the fundamental building blocks for general representations. Concretely, any representation of a compact group over a real vector space decomposes into a direct sum of irreps (Naimark & Stern. 1982; Bump, 2004). representation ı G GL(VV is irreducible if V is not 0 and if no vector subspace of V is stable under G. other than O and V (which are always stable under G). A subspace W being stable (or invariant) under G means that x (gg) un E W for all ur E W and g E The condition that the points (r) be in general position essentially means that there is no prescribed special relationship between the r and between the r" and (T). Taking the r to be drawn from a full-rank Gaussian distribution is sufficient to satisfy this condition.
Proof. By the theorem of complete reducibility (see Fulton & Harris (2004)), л admits a decomposi- tion into direct sum of irreps π _ Th₁ @ @T..B.kky acting on vector space V Vi V/2 @ VM, where _ denotes equality up to similarity transformation. The indices k; indicate the type of irrep corresponding to invariant subspace V,. The fixed point subspace Vú is the direct sum of subspaces where trivial kj- = O irreps act: Vo- = =o Vn. By the Grand Orthogonality Theorem of irreps (see Liboff (2004)) all non-trivial irreps average to zero (T),,1(9)) JEG X ōgg, Then, the matrix (T) simply projects the data to Vo. By Lemma the fraction of separable dichotomies
the m-- manifolds is the same as that of their centroids (Tr) Since, by assumption, the P points (T)r* lie
in general position in Vo, the fraction of separable dichotomies is f(P, dim Vo) by Equation 1. O
Remark: A main idea used in the proof is that only nontrivial irreps average to zero. This will be illustrated with examples in Section 4 below.
Remark: For finite groups. No can be easily computed by averaging the trace of æ,, also known as the character, over G: No = (II(T(())) = Tr((T)) (see Serre (2014)).
Remark: If the perceptron readout has bias term b i.e. the output of the perceptron is w (g)r(())+ then this can be thought of as adding an invariant dimension. This is because the output can be written w #(g)r where to = (w, b). F (r, 1), and (g) = x(g) @ 1 is π with an extra row and column added with a in the last position and zeros everywhere else. Hence the fraction of separable dichotomies is S(P, No + 1).
These results extend immediately to notion of VC-dimension of group-invariant perceptrons.
Corollary Let the VC dimension for G-imvariant perceptrons with representation n, Nic- denote the maximum number P, such that there exist P anchor points {r")p= so that (("(g)r"""")) (eE is separable for all possible binary dichotomies (y"))e(rr) Then NyC dom(Vo).
Proof. By theorem and Equation all possible dichotomies are realizable for P dim(Vo)
provided the points (m) pd are in general position.
Our theory also extends immediately to subgroups. For example, strided convolutions are equivari- ant subgroups of the regular representation.
Corollary 2. A solution to the the G-invariant elassification problem necessarily solves the G'- invariant problem where G' is a subgroup of G.
Proof. Assume that you T Tr(aa)) > 0 for y E G. G G = y0 (u(T(")))))))))) > 04 E O
Consequently, the G' G'-invariant capacity is always higher than the capacity for the G-invariant clas- sification problem.
5

---

Published as a conference paper at ICLR 2022
(d)
(b)
(c)
72
T3
T'
10
60
T1 95
-10
72 71
7'2
71
Figure 1: m-manifolds for different illustrating that only the fixed point subspace contributes to capacity. In each panel two manifolds are plotted, with color denoting class label. Stars indicate the random points pP for μ {1, 2} where the orbits begin, and closed circles denote the other points in the m-manifold. For (a) and (b) the group being represented is G = Z4 and for (c) G = Z3. (a) Here (g) the 2 x rotation matrix R R( /4) The open blue circle denotes the fixed point subspace (0). (b) Here (g)) is the 3 x 3 block-diagonal matrix with the first 2 x 2 block being R(2rg/4) and second
1 block being 1. The blue line denotes the fixed point subspace span (0, O, 1)}. (c)
Here x (g) is the 3 x 3 matrix that cyclically shifts entries of length-3 vectors by places. The blue line denotes the fixed point subspace span ( (,,,
EXAMPLE APPLICATION: THE CYCLIC GROUP Zm
In this section illustrate the theory in the of the eyclic group G = Z,. m elements. This group is isomorphic to the group of integers {0, ...,, m - 1} under addition modulo m, and this the form of the group that will consider. An example of this group acting object is an image that is shifted pixel-wise to the left and right, with periodic boundaries. In Appendix A.3 we show application of theory the non-abelian Lie group SO(3).
4.1 ROTATION MATRICES
The 2 x 2 discrete rotation matrices R(Og) cos((0 sin (0n) sin (g)
cos( Og)) where 0g = 2xg/m and
E Zm. one possible representation of 7m: in this case V R.2. This representation is irreducible and nontrivial, which implies that the dimension of the fixed point subspace is (only the origin mapped itself by R for all g). Hence the fraction of lincarly separable dichotomies of the m-manifolds by Theorem is f(P, 0). This result can be intuitively seen by plotting the orbits, as in Figure la for manifolds with different class labels, and that the nontrivial irrep R averages to the zero matrix.
4. Here it is apparent that is impossible linearly separate two more
The representation can be augmented by appending trivial irreps, defining G GL(R by T (g) R(0g) + R(O,) 0) where I is an (N 2) x (N - -)ddimmnsio identity matrix.
0
The number of trivial irreps is N 2, so that the capacity is s(P, N - 2). This is illustrated in Figure lb for the
N = Here span((0) (0, 0, 1)), is the only irrep in the decomposition of that does not average to zero. This figure also makes intuitive the result of Lemma that dichotomies are realizable on the 7-manifolds if and only if the dichotomies are realizable on the centroids of the manifolds.
also that the trivial irrep, which acts the subspace
4.2 THE REGULAR REPRESENTATION OF Zm
Suppose : Zm - GL(V) is the representation of Zm consisting of the cyclic shift permutation matrices (this is called the regular representation of Zm). In this case V R and (()) is the matrix that eyclically shifts the entries of a length-m vector 9 places. For instance, if m 3 and
v = (1,2,3) then π (2)u = (,,3,1)
In Appendix A.2 derive the irreps of this representation, which consist of rotation matrices of different frequencies. There one copy the trivial irrep To(g) = corresponding with the fixed point subspace spanç1, (Im) where I is the length-m all-ones vector. Hence the fraction of separable

---

Published as a conference paper at ICLR 2022
dichotomies is f(P.1). This is illustrated in Figure Ic in the case where = 3. The average of the regular representation matrix is (T) 1m I. indicating that (T) projects data along 1m.
4.3 DIRECT SUMS OF REGULAR REPRESENTATIONS
For our last example we define a representation using the isomorphism Zm = Zmy @ Zmg for my m2 and m and m2 coprime.. Let x(1), Zm, - GL( and π x Zmma + GL be the cyclic shift representations (i.e. the regular representations) of Zm, and Zmy respectively. Consider the representation (1)) @T(2); Zm + GL +m²) defined by (r()))(()))())))) = 7() mod m1) @ (g mod m2), the block-diagonal matrix with (1))gg mod m1) being the first and T (2) [g mod m2) the second block.
There are two copies of the trivial representation in the decomposition of x1)) ( xt x22), correspond-
ing to the one-dimensional subspaces span (1 m 0mg)} } and span (0m; [mmm)) )}. where Om, is the length-k vector of all zeros. Hence the fraction of separable dichotomies is ((P22) This reasoning
extends simply to direct sums of arbitrary length É, yielding fraction of f(P, E). These representa-
tions are used to build and test a novel G-convolutional layer architecture with higher capacity than standard CNN layers in Section 5.
These representations are analogous to certain formulations of grid cell representations as found in entorhinal cortex of rats (Hafting al., 2005), which have desirable qualities in comparison to place cell representations (Sreenivasan & Fiete, 2011). Precisely, a collection {mm, x Z h& of grid cell modules encodes large 2-dimensional spatial domain Zm x Z. where
1 mg.
G-EQUIVARIANT NEURAL NETWORKS
The proposed theory can shed light on the feature spaces induced by G-CNNs. Consider a single convolutional layer feature map for a finite" group G with the following activation
0i (ar) <b(w, 9ú '=:) Ik E G,, i N1,
for some nonlinear function Φb For each filter i, and under certain choices of u. the feature map ax(x) E R/Gl exhibits the equívariance property (=(g)=)) ((g))a (x;). We will let a(x) E R G| denote a flattened vector for this feature map.
In traditional periodic convolutional layer applied to inputs of width W and length L, the feature map of single filter (x) R is equivariant with the regular representation of the group G = Zw x Z (the representation that cyclically shifts the entries of W x matrices). Here the order of the group is G| W L. Crucially, our theory shows that this representation contributes exactly one trivial irrep per filter (see Appendix 1.4.1). Since the dimension of the entire collection of N feature maps a(x) is N|G] for finite groups G, one might naively expect capacity to be P ~ 2N G for large N from Gardner (1987). However, Theorem shows that for G-invariant classification, only the trivial irreps contribute the classifier capacity. Since the number of trivial irreps present in the representation is equal to the number of filters N, we have P ~ 2N.
We show in Figure 2 that our prediction for (P,.N) matches that empirically measured by training logistic regression linear classifiers on the representation. We perform this experiment on both (a) a random convolutional network and (b) VGG-11 (Simonyan & Zisserman, 2015) pretrained on CIFAR-10 10 (Krizhevsky, 2009) by (liukuang. 2017). For these models we vary by fixing the number of input samples and varying the number of output channels by simply removing channels from the output tensor. The convolutions in these networks are modified to have periodic boundary conditions while keeping the actual filters the same see Appendix A.4. I and Figure A. for more information and the result of using non non-pooiodic convolutions, which impact the capacity but not the overall scaling with No-
Two numbers are coprime they have no common prime factor.
"Our results do not actually require that the m& be coprime, but rather that none of the my divide one of the others. To see this, take mn and ma, be m and the mą after being divided by all divisors common among them. Then Z.. S Zi, and provided none of the me are 1, one still gets fraction of [PP, E).
Place cells are analogous to standard convolutional layers.
We consider finite groups here for simplicity, but the theory extends to compact Lie groups
7

---

Published as a conference paper at ICLR 2022
Other GCNN architectures can have different capacities. For instance, a convolutional layer equiv- ariant to the direct sum representation of Section 4.3 has double the capacity with P ~ 4N (Fig- ure 2c), since each output channel contributes two trivial irrep.. See Appendix A.4.4 for explicit construction of such a convolutional layer and a derivation of the capacity.
5.1 POOLING OPERATIONS
In convolutional networks, local pooling is typically applied to the feature maps which result from each convolution layer. In this section, we describe how our theory can be adapted for codes which contain such pooling operations. We will first assume that is an N-dimensional representation of G. Let Prr)= TR N/ be pooling operation which reduces the dimension of the feature map. The condition that given dichotomy {v") is linearly separable on a pooled code is
Ew E R// Vp E [P].9 E G y"u T (((T(grr*) >
(3)
We will first analyze the capacity when P(.) is linear function (average pooling) before studying the more general case of local non-linear pooling on one and two-dimensional signals.
5.1.1 LOCAL AVERAGE POOLING
In the case of average pooling, the pooling function P()) is a linear map, represented with matrix P which averages a collection of feature maps over local windows. Using argument similar to Lemma 1 (Lemma/ and Theorem 2 in Appendix A.4.2), we prove that the capacity of a standard CNN is not changed by local average pooling: for network with N filters, local average pooling preserves the one trivial dimension for each of the N filters. Consequently the fraction of separable dichotomies is (P, N).
5.1.2 LOCAL NONLINEAR POOLING
Often, nonlinear pooling operations are applied to downsample feature maps. For concreteness, will focus on one-dimensional signals in this section and relegate the proofs for two-dimensional signals (images) to Appendix A.4.2. Let r(x) E B- x represent feature map with N filters and length-D signals. Consider a pooling operation P(-) which maps the D pixels in each feature map into new vectors of size D D/k for some integer k. Note that the pooled code is equivariant to the subgroup H DD/ in the sense that (h)r)) = p(h))P(r) for any h E H. The representation is the regular representation of the subgroup H. We thus decompose G into cosets of size D/K: g = jh, where j Zy and Zpik. The condition that vector w separates the dataset
Vp E [P],j E ZE, E H y" p(h)) (T(i)"") > O.
(4)
We that there are effectively l points belonging to each of the P orbits in the pooled code. Since P (-) is nonlinear, the averaging trick utilized in Lemma is no longer available. However, we can obtain lower bound on the capacity, f(P, [N/k]] ), from simple extension of Cover's original proof technique as we show in Appendix A.4.3. Alternatively, an upper bound f < S(P, N) persists since w which satisfies Equation 4 must separate (o(h)))e P(r#). This upper bound is tight when all ls points (p(h)) P()(j)r") coincide for each μ. giving capacity f(P,N) P). This is what occurs in the average pooling case where the upper bound f < f(P, N) is tight. Further, if we are only interested in the -iinvariant capacity problem, the fraction of separable dichotomies is NN,,,, since p is regular representation of H show in 4.
5.1.3 GLOBAL POOLING
Lemma shows that linear separability of r-manifolds is equivalent to linear separability after global average pooling (i.e. averaging the representation over the group). This is relevant CNNs, which typically perform global average pooling following the final convolutional layer, which is typically justified by a desire to achieve translation invariance. This strategy efficient: Lemma implies that it allows the learning of optimal linear readout weights following the pooling operation, given only a single point from each π r-manifold (i.e. no need for data augmentation). Global average pooling reduces the problem of linearly classifying |G| P points in space of dimension N to that of linearly classifying points in a space of dimension dim Vo. Note that by an argument similar to Section 5.1.2, global max pooling may in contrast reduce capacity.
8

---

Published as a conference paper at ICLR 2022
(8)
(b)
(c) 10
Retl theory maagpol
blokk Sheory
gidies
0.8
0.8
care block
0.8
came -ULL
0.0
06
010
0.0
0.0
083
1.0
1.5
2.0
2.5
3.0
0.5
1.0
1.3
2.0 P/No
25
P/N2
P/No
Figure 2: Capacity of GCNN representations, Solid lines denote the empirically measured fraction fa) of 100 random dichotomies for which logistic regression classifier finds separating hyper- P/No- Dotted lines denote theoretical predictions. Shaded regions depict 95%
plane, where confidence intervals over random choice of inputs, as well as network weights in (a) and (c). (a) fa) of random periodic convolutional layer after ReLU (blue line) and followed by 2x2 max pool (orange line), with P = 40 and N, = # output channels. Max pooling reduces capacity by a factor between 1/4 and predicted by theory. (b) f(a) of VGG-11 pretrained periodic convolution, batchnorm, and ReLU (blue line), followed by a 2x2 maxpool (orange line), and then another set of convolution, batchnorm, and ReLU (green line), with P = 20 and No- output channels. Max pooling reduces capacity as predicted. (c) f(a) after random convolutional layer equivariant to the direct sum representation of Z1o Zg defined in Section 4.3, with P 16 and No = 2 (# output channels).
CIFAR-10 1- after
5.2 INDUCED REPRESENTATIONS
Induced representations are a fundamental ingredient the construction of general equivariant neu- ral network architectures (Cohen et al., 2019b). Here we state our result, and relegate a formal definition of induced representations and the proof of the result to Appendix A.4.5.
Let be a representation of finite group induced from p. Then the fraction of separable dichotomies of x-manifolds is equal to that of the p-manifolds.
Proposition 1.
DISCUSSION AND CONCLUSION
Equivariance has emerged as a powerful framework to build and understand representations that re- flect the structure of the world in useful ways. In this work we take the natural step of quantifying the expressivity of these representations through the well-established formalism of perceptron ca- pacity. We find that the number of "degrees of freedom" available for solving the classification task is the dimension of the space that is fixed by the group action. This has the immediate implication that capacity scales with the number output channels in standard CNN layers, fact we illustrate in simulations. However, our results also very general, extending to virtually any equivariant representation of practical interest in particular, they are immediately applicable to GCNNs built around general equivariance relations, to direct sum representations. We also calculate the capacity of induced representations, a standard tool building GCNNs, and show how local and global pooling operations influence capacity. The measures of expressivity explored here could prove valuable for ensuring that models with general equivariance relations have high enough capacity to support the tasks being learned, either by using more filters or by using representations with intrinsically higher capacity. We leave this to future work.
illustrate with an example of GCNN equivariant
While the concept of perceptron capacity has played an essential role in the development of machine learning systems (Schölkopf Smola, 2002; Cohen al., 2020) and the understanding of biolog- ical circuit computations (Brunel et al., 2004; Chapeton et al., 2012; Rigotti et al., 2013; Brunel, 2016; Rubin et al., 2017; Pehlevan & Sengupta, 2017: Lanore et al., 2021; Froudarakis al., 2020), more work is wanting in linking it to other computational attributes of interest such as generaliza- tion. A comprehensive picture the computational attributes of equivariant or otherwise structured representations of artificial and biological learning systems will likely combine multiple measures, including perceptron capacity. There is much opportunity, and indeed already significant recent work (e.g. Sokolic et al. (2017)).

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Code for the simulations can be found at https://github.ce group- iim--niiaiinn peettteereoeooo capacity. This code includes an environment.ym file that can be used to create python environment identical to the one used by the authors. The code generates all of the plots in the paper.
While the main text is self-contaings with the essential proofs, proofs of additional results and further discussion can be found in the Appendices below. These include
Appendix A.1
glossary of definitions and notation.
Appendix A.2 derivation of the irreps for the regular representation of the cyclic group 7m
Appendix A.3 a description of the irreps for the group SO(3) and the resulting capacity.
Appendix A.4 a description of the construction the GCNNs used in the paper, the methods for empirically measuring the fraction of linearly separable dichotomies, a description of local pooling, and complete formal proofs of the fraction of linearly separable dichotomies for these network representations (including with local pooling). This appendix also includes more description of the induced representation and a formal proof of the fraction of linearly separable dichotomies.
Appendix A.4.1 also contains an additional figure, Figure A.I.
ACKNOWLEDGEMENTS
MF and CP are supported by the Harvard Data Science Initiative. MF thanks the Swartz Foundation for support. BB acknowledges the support the NSF-Simons Center for Mathematical and Statis- tical Analysis of Biology Harvard (award #1 #1764269) and the Harvard Q-Bio Initiative. ST was partially supported by the NSF under grant No.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Yaser S. Abu-Mostafa. Hints and the VC Dimension. Neural Computation, 5(2):278-288) 03 1993. ISSN 0899-7667. doi: 10.1162/neco. 1993.5.2.278. URL https:/ http://.......10111111111
Yaser Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin. Learning from data, volume 4. AMLBook New York, NY, USA:, 2012.
Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buc, Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Minkyung Baek, Frank Dimaio, Ivan V. Anishchenko, Justas Dauparas, Sergey Ovehinnikov, Gyu Rie Lee, Jue Wang, Qian Cong, Lisa N. Kinch, Dustin Schaeffer, Claudia Millán, Hahn- beom Park, Carson Adams, Caleb R. Glassman, Andy M. DeGiovanni, Jose H. Pereira, An- dria V. Rodrigues, Alberdina Aike van Dijk, Ana Ebrecht, Diederik Johannes Opperman, Theo Sagmeister, Christoph Buhlheller, Tea Pavlov-Keller, Manoj K. Rathinaswamy, Udit Dalwadi, Calvin K. Yip. John E. Burke, K. Christopher Garcia, Nick V. Grishin, Paul D. Adams, Randy J. Read, and David Baker. Accurate prediction of protein structures and interactions using three- track neural network. Science, 373:871 876, 2021.
Eric B. Baum. On the capabilities of multilayer perceptrons. J. Complex., 4: 4:193-215, 1988.
Erik J. Bekkers, Maxime W. Lafarge, Mitko Veta, Koen A. Eppenhof, Josien W. Pluim, and Remco Duits. Roto-translation covariant convolutional networks for medical image analysis. ArXiv, abs/aabs.... 004.03904.3393, 2018.
Alexander Bogatskiy, Brandon Anderson, Marwah Roussi, David Miller, and Risi Kondor. Lorentz group equivariant neural network for particle physics. In International Conference Machine Learning, pp. 992-1002. PMLR, 2020.
Nicolas Brunel, Vincent Hakim, Philippe Isope, Jean-Pierre Nadal, and Boris Barbour. Optimal information storage and the distribution of synaptic weights: perceptron versus purkinje cell. Neuron, 43(5):745-757, 2004.
Nicolas J.-B. Brunel. Is cortical connectivity optimized for storing information? Nature Neuro- science, 19:749-755 -559997552200 2016.
Daniel Bump. Lie groups, volume 8. Springer, New York, 2004. ISBN 9781475740943.
Julio Chapeton, Tarec Fares, Darin LaSota, and Armen Stepanyants. Efficient associative memory storage in cortical circuits of inhibitory and excitatory neurons. Proceedings of the National Academy of Sciences, 109:E3614 - E3622, 2012.
Shuxiao Chen, Edgar Dobriban, and Jane Lee. A group-theoretic framework for data augmen- tation. In H. Larochelle, M. Ranzato, Hadscll, M. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21321-21333, Curran As- sociates, Inc., 2020. URL https: htt.ttpss//pprcceddiggggoeseeeee www.:eeeeeddinn...eeee.eee...ee. cc wttpp/appe//22///iieeee.. .ddf.
Yeo Chung, Daniel D. Lee, and Haim Sompolinsky. Classification and Geometry of General Perceptual Manifolds. Physical Review X, 8(3):031003, July 2018. doi: 10.1103/Physevv..88 031003.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In ICML, 2016.
Taco Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. ArXiv, abs//a00...... 1801. 2018.
Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convolu- tional networks and the icosahedral enn. In ICML, 2019a.

---

Published as a conference paper at ICLR 2022
Taco S Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant CNNs ho- mogeneous spaces. In H. Wallach, H. Larochelle, A. Beygelzimer, dAlché-Bue Buc, Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019b.
Uri Cohen, Sue Yeon Chung, Daniel D. Lee, and Haim Sompolinsky. Separability and geometry of object manifolds in deep neural networks. Nature Communications, 11(1):746, February 2020. ISSN 2041-1723. doi: 10. 00.10088/411467-000-445733 145-----
T. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Trans. Electron. Comput.. 14:326-323 -344, 1965.
John Denker, W. Gardner, Hans Graf, Donnie Henderson, R. Howard, W. Hubbard, L. D. Jackel, Henry Baird, and Isabelle Guyon. Neural network recognizer for hand-written zip code digits. In D. Touretzky (ed.), Advances in Neural Information Processing Systems, volume 1. Morgan- Kaufmann, 1989. URL a97da (97da629b0985 5c2 94df f4wdffdcee43390000 2aa1663900---ar.......
/ttp://///coccceongs..o.o www.diiiiiinnnnereeoeeeeeeeeeeee cc wwtppppp/////e/eeccccccccce.eeee 19t.//918//// 119988/fi0 /ate//fll/////
James J DiCarlo and David D Cox. Untangling invariant object recognition. Trends in cognitive sciences, 1 (13))333-341, 2007.
Alexander S Ecker, Fabian H Sinz, Emmanouil Froudarakis, Paul G Fahey, Santiago A Cadena, Edgar Y Walker, Erick Cobos, Jacob Reimer, Andreas S Tolias, and Matthias Bethge. A rotation-equivariant convolutional neural network model of primary visual cortex. arXiv preprint wrXiv:180.110044 2018.
Stephan Fismann, Raphael J. L.. Townshend, Nathaniel Thomas, Milind Jagota, Bowen Jing, and Ron O. Dror. Hierarchical, rotation-squivariant neural networks to select structural models of protein complexes. Proteins: Structure, 89:493 501, 2020.
Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2959-2969. PMIR, 2021. URL http: / proceed ngs. html.
mlr.
Carlos Esteves, Christine equivariant representations with spherical cnns. In ECCV, 2018.
Ameesh Makadia, and Kostas Danilidiss Learning so(3)
Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convo- lutional neural networks for equivariance to lie groups arbitrary continuous data. In ICML, 2020.
Marc Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equiv- ariant multilayer perceptrons for arbitrary matrix groups. ArXiv, abs/2104.09459, 2021.
Emmanouil Froudarakis. Uri Cohen, Maria Diamantaki, Edgar Y Walker, Jacob Reimer, Philipp Berens, Haim Sompolinsky, and Andreas S Tolias. Object manifold geometry across the mouse cortical visual hierarchy. bioRxiv, 2020.
William Fulton and Joe Harris. Representation Theory: First Course. Readings in Mathematics. Springer- Verlag New York, New York, 2004. ISBN 9780387974958.
E. Gardner. Maximum storage capacity in neural networks. EPL, 4:481-488 1987.
E. Gardner. The space of interactions in neural network models. Journal of Physics A, 21:257-270, 1988.
Jonathan Gordon, David Lapez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivari- ant models for compositional generalization in language. In ICLR, 2020.
Torkel Hafting, Marianne Fyhn, Sturla Molden, May-Britt Moser, and Edvard I. Moser. Microstruc- ture of a spatial map in the entorhinal cortex. Nature, 436(7052):801-806 August 2005. ISSN 0028-0836, 1476-4687. doi: 10.1038.nauur00321..
12

---

Published as a conference paper at ICLR 2022
Jason S. Hartford, Devon R. Graham, Kevin Leyton- (iooon- and Siamak Ravanbakhsh. Deep models of interactions across sets. In JCML, 2018.
John Hertz, Anders Krogh, and Richard G Palmer. Introduction to the theory of neural computation. CRC Press, 2018.
Guangbin Huang. Learning capability and storage capacity of two-hidden-layer feedforward net- works. IEEE transactions neural networks, 14 2:274-81, 2003.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural net- works. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: / http:/ppoceeeigggeeeeee Paper. pdf.
ular graphs. ArXiv, (152268003555lll122222eeeeeeeda3 http:eaeeeeebbttttpaa.....eee
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molec- 2020.
Risi Kondor and Shubhendu Trivedi. On the generalization of cquivariance and convolution in neural networks to the action of compact groups. In ICMI., 2018.
Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-gordan nets: a fully fourier space spherical convolutional neural network. In NeurlPS, 2018a.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon M. Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. ArXiv, abs/1 11211801.00 .21144, 2018b. 8b.
A. Kowalczyk. Estimates of storage capacity of multilayer perceptron with threshold logic hidden units. Neural networks: the official journal of the International Neural Network Society, 10 8: 1417-1433, 1997.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Frederic Lanore, Alex Cayco-Gajic, Harsha Gurnani, Diccon Coyle, and R. Angus Silver. Cere- bellar granule cell axons support high nigh-dimensional representations. Nature Neuroscience, June 2021. ISSN 1097-6256, 1546- 1726. doi: 10. 10110///41193-021-0050
Yann André LeCun, Bernhard E. Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne F. Hubbard, and Lawrence D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1:541-551, 1989.
Richard L. Liboff. Primer for Point and Space Groups. Undergraduate Texts in Contemporary Physies. Springer, New York, 2004, ISBN 9780387402482.
liukuang.
https:
2017.
Clare Lyle, Mark van der Wilk, Marta Z. Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. ArXiv, abs/2005.0017 2020.
George W. Mackey. Induced Representations of Locally Compact Groups and Applications, pp. 132-166. Springer Berlin Heidelberg, Berlin, Heidelberg, 1970. ISBN 978-3-642-
48272-4. doi: 00.100779788-3644--62222 978 1--3--64222 642-44244 222-48272-222 4_
URL
Diego Marcos, Benjamin Kellenberger, Sylvain Lobry, and Devis Tuia. Scale equivariance in enns with vector fields. ArXiv, 117718887. 2018.
Haggai Maron, Heli Ham-H Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ArXiv, abs/1812.09991) 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality invari- ant networks. In Proceedings of the 36th International Conference Machine Learning, vol- ume 97, pp. 4363-4371 PMLR, 2019b. URL attps:/ //ppoceedinggs..cc////// mir. r. w.ppess//77/ ma maron1 9a. html.
13

---

Published as a conference paper at ICLR 2022
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. ArXiv, abs/2002.08599, 2020.
Mark Aronovich Naimark and Aleksandr Isaakovich Stemn Theory of group representations, volume 246. Springer, New York, 1982. ISBN 9781461381440.
Mauro Pastore, Pietro Rotondo, Vittorio Erba, and Marco Gherardi. Statistical learning theory of structured data. Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisci- plinary Topics, 102(3):032115) 119, September 2020. doi: 10.1 1t000//PhyyyeeE112..0002222
Cengiz Pehlevan and Anirvan M. Sengupta. Resource-efficient perceptron has sparse synaptic weight distribution. 2017 25th Signal Processing and Communications Applications Conference (SIU), pp. 1-4, 2017.
Nathanael Perraudin, Michaël Defferrard, Tomasz Kacprzak, and Raphael Sgier. Deepsphere: Effi- cient spherical convolutional neural network with healpix sampling for cosmological applications. Astron. Comput., 27:130-146, 146,0-1662220 2019.
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7996-8006. PMLR, 13-18 Jul 2020. URL https::
mlr http:///sw....tt.....eo////////a
html.
Mattia Rigotti, Omri Barak, Melissa R Warden, Xiao-Jing Wang, Nathaniel D Daw, Earl K Miller, and Stefano Fusi, The importance mixed selectivity in complex cognitive tasks. Nature, 497 (7451):585 5900 2013.
Pietro Rotondo, Marco Cosentino Lagomarsino, and Marco Gherardi. Counting the learnable func- tions of geometrically structured data. Physical Review Research, 2(2):023169, May 2020. doi: 10.1 Rere///hyyeeeeserrch.2.22000
Ran Rubin, L. F. Abbott, and Haim Sompolinsky. Balanced excitation and inhibition required for high-capacity, noise-robust neuronal selectivity. Proceedings of the National Academy of Sciences, 14:193366 2017.
Akiyoshi Sannai, M. Imaizumi, and M. Kawano. Improved generalization bounds of group invariant / equivariant deep networks via quotient feature spaces. 2019a.
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. ArXiv, abs/1903.01939, 2019b.
Victor Garcia Satorras, E. Hoogeboom, F. Fuchs, I. Posner, and M. Welling. E(n) equivariant nor- malizing flows for molecule generation in 3d. ArXiv, abs/2105.09016, 2021.
Ludwig Schläffi. Theorie der vielfachen Kontinuität, pp. 167-387. Springer Basel, Basel, 1950. doi: 10. 100009978---0048--411 411 8-4_13.
ISBN 378-3-0348-411844
13. URL httpps://de /ttp:///////////////oo/..oo
Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regularization. Optimization, and Beyond. Adaptive Computation and Machine Learning, MIT Press, 2002. ISBN 978-0-262-19475-44
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. ArXiv, abs/1910.02221, 2020.
Jean-Pierre Serre. Linear Representations of Finite Groups. Graduate Texts in Mathematics. Springer, New York, 2014. ISBN 978-1-4684-94660- 978-1-4668-9955-77
H Sebastian Seung and Daniel D Lee. The manifold ways of perception. science, 290(55000:2268. 2000.
John Shawe-Tayy Taylor. Threshold network learning in the presence of equivalences. In NIPS, 1991.
14

---

Published as a conference paper at ICLR 2022
Mariya Shcherbina and Brunello Tirozzi. Rigorous Solution of the Gardner Problem. Com- munications in Mathematical Physics, 234(3):383-42 March 2003. ISSN 0010-3616, 1432- 0916. doi: 10. 000000//000000000000707013311110 URL http://lintt springer wtwpi/ger.comm....11.... s00220- 0783-3.
N. Shutty and Casimir Wierzynski. Learning irreducible representations of noncommutative lie groups. ArXiv, abs/2006.00724 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409, 1556, 2015.
Bart Smets, Jim Portegies, Erik J. Bekkers, and Remco Duits. Pde-based group equivariant convo- lutional neural networks, ArXiv, abs/2001 2020.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization Error of In- variant Classifiers. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statisties, volume 54 of Proceedings of Machine Learn- ing Research, pp. 1094-1103, 103. PMLR, 20-22 Apr 2017. URLhttps: h/tp:s/sss//.ooceeinggg... mlr. press/ v www.ooococccccccooooocooaccoocca 7a .tmhmml.
Eduardo Sontag. Shattering all sets of points in general position requires (k 1)/2 parameters. Neural Computation, 9:337-348, 1997.
I. Sosnovik, A. Moskalev, and A. Smeulders. Scale equivariance improves siamese tracking. 2021 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 2764-2773, 2021.
Ivan Sosnovik, Michal Szmaja, and Arnold W. Smeulders. Scale-equivariant steerable networks. ArXiv, abs/1910.1 1093, 2020.
Sameet Sreenivasan and Ila Fiete. Grid cells generate analog error-correcting code for singularly precise neural computation. Nature Neuroscience, 14(10))1330-1333 October 2011. ISSN 1097- 6256, 1546- 1726. doi: 10.1038/nn.2901.
Raphael L. Townshend, Stephan Eismann, Andrew M. Watkins, Ramya Rangan, Maria Karelina, Rhiju Das, and Ron O. Dror. Geometric deep learning of rna structure. Science, 373:1041 1051, 2021.
Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the uniform convergence of relative frequen- cies of events to their probabilities. Dokl. Akad. Nauk., 181(4), 1968.
Bastiaan Veeling, Jasper Linmans, Jim Winkens, Taco Cohen, and Max Welling. Rotation equiv- ariant cnns for digital pathology. ArXiv, htss/800.03362,, 2018.
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Math. Data Sci., 2:1004-1033, 2020.
Maurice Weiler and Gabriele Cesa. General e(2)-equivariant steerable cnns. ArXiv, abs/ 191199110000 088211 2019.
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data. In NeurlPS, 2018a.
Maurice Weiler, Fred A. Hamprecht, and Martin Storath. Learning steerable filters for rotation equivariant cnns. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 849 0599-558,20 2018b.
Maurice Weiler, Patrick Forré, Erik Verlinde, and Max Welling. Coordinate independent convolu- tional networks isometry and gauge equivariant convolutions on riemannian manifolds. ArXiv, abs/2106.06020, 2021.
G. Wendel. A problem in geometric probability. Mathematica Scandinavica, 11:109-112, 1962.
Eugene Wigner.
Gruppentheorie Und Ihre Anwendung Auf Die Quantenmechanik Der Atomspek- fren. Vieweg+TTeubner Verlag, Wiesbaden, first edition, 1931. ISBN 978-3-663-00642-8.
15

---

Published as a conference paper at ICLR 2022
Marysia Winkels and Taco Cohen. Pulmonary nodule detection in scans with equivariant cnns. Medical image analysis, 55:15-26, 2019.
Daniel E. Worrall and Gabriel J. Brostow. Cubenet: Equivariance to 3d rotation and translation. In ECCV, 2018.
Daniel E. Worrall and Max Welling. Deep scale-spaces: abs/1905.11660 1657,, 2019.
Equivariance over scale. ArXiv,
Daniel E. Worrall, Stephan J. Garbin, Daniyar Turmukhambetov, and Gabriel J. Brostow. Harmonic networks: Deep translation and rotation equivariance. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 7168-716777 -1777 2017.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. ArXiv, abs/1804.10366, 2018.
Chulhee Yun, S. Sra, and A. Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. In NeurIPS, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alex Smola. Deep sets. In NIPS, 2017.
16

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 NOTATION AND GLOSSARY
æ: an abstract notation for an input object
raz): feature map of the input an N dimensional vector space.
N dimensional linear representation of group G. For each G. (()) E GL(RR) is an N x N invertible real matrix.
Equivariance property: r(ga) n (())r())) for all g and x.
Invariant measure: measure μ G + R+ on G with p(gS) pts) ((gg). For finite groups, the uniform distribution. For locally compact topological groups, the Haar measure.
D an average over the invariant measure of G
Irreducible representation (irrep): an irreducible representation p on vector space satis- fies p(g) E V for all V,g G.
Character xg):: the trace of the representation X(9) = Tr Tg)).
Fixed point subspace: the subspace Vo for which <(g) E Vo for all v E Vo.
General position: a collection of points in general position in an N dimensional vector space have the property that any subset of k S N points are linearly independent. These points are generic in the sense that they satisfy no more linear relationships than they must.
Dichotomy: a particular binary labeling {v") of P points {ø"}.
f(P, fraction of linearly separable dichotomies given by Cover's function counting
theorem (Cover, 1965).
VC dimension: the largest possible integer P such that there exist P points where all possible dichotomies {y") can be realized by the model Abu-Mostafa et al. (2012).
Capacity: the largest possible ratio a₂ P/N where P points in general position can be linearly separated by a N dimensional perceptron with probability an asymptotic limit where P, + do with P/N (1.) The classical result is a. 2 (Gardner, 1987; Shcherbina & Tirozzi, 2003).
P(-): local pooling operation.
A.2 IRREPS FOR THE CYCLIC GROUP
Here we compute the irreps of representations क 7.m - GL(V) of the cyclic group Z, over real vector space V (see (Serre, 2014) for a derivation of the irreps when V is a complex vec- tor space). To find the irreps, one can use the form for the eigenvalues and eigenvectors for cir- culant matrices, since all the (g) are circulant. This results in the simultaneous diagonalization (g) = V (1 e R(2gg/m @ R(4ng/ valued version of the discrete Fourier transform matrix (the columns are proportional cosines and sines of varying frequencies, along with a column proportional to 1mm).
@ ... C R(mm 1)Tg/mm m)) V where V is the real-
Note that the 2r2 rotation matrices R(2ngh: gk/m)///)))) irreps for k * m/2 and k * 0, since there no one-dimensional subspace of R2² that invariant to R(2ngk/m for all g. The exception for k m/2 if m is even, gives R(2ngk/m)
(-1)aI, which corresponds rotation of 180 degrees. The subspace span (1, is invariant to this action, so that R(27gk/m) is not an irrep. This representation can thus be reduced an action one-dimensional subspace, represented by (-1)9. The case k = 0 gives the trivial representation.
A.3 SO(3): A NON-ABELIAN LIE GROUP
The special orthogonal group SO(3) on dimensions (rotation group), the x orthogonal ma- trices with determinant +1, can also be analyzed within theory. G-convolutional neural net- works that are equivariant to (O(3) rotations have become of high interest in the physical sciences and computer vision where the objects of interest often respect these symmetries (Anderson al.,
17

---

Published as a conference paper at ICLR 2022
2019: Cohen et al., 2018; Esteves et al., 2018; Kondor et al., 2018a) The irreducible representations have the form Bx... where Bb... are (2km + x (2km + 1) block matrices, known as Wigner D- matrices (Wigner, 1931). The trivial irreps correspond to the one-dimensional irreps with & 0. Thus, the (O(3)-invariant classification capacity merely counts the number of trivial irreps which have No- Lm Ōk.,.0- The capacity is again [(P,No)
A.4 G-RQUIVARIANT CONVOLUTIONAL. LAYERS
A.4.1 STANDARD CONVOLUTIONAL LAYERS
A convolutional layer consists of a set of N k x filters F. that are convolved (technically cross- correlated) with stack of M W X L input tensors. Here M is the number of input channels and N the number of output channels. The convolution runs each filter (i.e. takes the dot product at all possible positions) over each of the W L input tensors, and the result is averaged across the M input channels to produce the output of one output channel. In the positions where the filters approach the edges of the input tensor, different choices can be made about how to handle these edge conditions. The standard choice is to pad the edges with some number of zeros depending on the desired shape of the output tensor and run the convolution out the end of the padded image. Another possible choice is to loop the edges of the imput tensor together, so that the filter is applied to the other side of the input tensor as runs off the edge. This periodic boundary condition allows us to write the convolution formally in terms of group actions, and to apply our theory directly. When convolutions are not periodic, the resulting capacity increases somewhat but still follows the P/No scaling of the periodic convolutions (Figure A.
For the random convolutional layers of Figure 2a, the input tensors are size 10 x 10 and the number of input channels are M = 3, as for standard color images. Each entry of these tensors is normally distributed with mean O. The filters are also of size 10 x 10 with periodic boundary conditions, and are initialized according to normal Xavier distribution with parameters that are the default for Pytorch 1.9. The convolution is implemented via the Pytorch 1.9 implementation of Conv2d with padding mode="cireellar" and padding=0 in the case of periodic boundary conditions. The bias term of the convolution is set to zero and the convolution is followed by a ReLU nonlinearity (blue line). The resulting figures do not change appreciably for different choices of input tensor size, number of input channels, or size of filters (though note that the nonlinearity is essential for satisfying the gen- eral position condition of Theorem 1; otherwise, the capacity would be determined by the number of input channels rather than number of output channels). The output of this convolution is then fed through a 2 x 2 max pooling layer (orange line in Figure 2a), provided by Pytorch 1.9's MaxPool2d.
The pretrained VGG-11 I layers used in Figure 2b and Figure A. are taken from liukuang (2017). The first convolutional block (blue line) consists of 3 x 3 pretrained filters applied to CIFAR-10 image tensors randomly selected from the validation set and normalized in the same way they are normalized during training (see liukuang (2017) for details). These images are of size 32 x 32 and have M = 3 input channels, followed by a batch normalization layer in evaluation mode (fixed parameters), and then followed by a ReLU nonlinearity. The boundary conditions of these convolu- tions are set to be periodic in Figure 2b and nonperiodic with zero padding sizes of 1 in Figure A. and the bias term is set to zero. The batch normalization an glement-wist wise operation and so equiv- ariant to the representations we consider thus this operation is not expected and is not observed to affect the perceptron capacity. This convolutional block is then followed by a 2 x 2 max pooling layer (orange line). Finally, another convolutional block of 3 filters, batch normalization, and ReLU nonlinearity are applied (green line).
The fraction of linearly separable dichotomies is measured empirically by using the scikit-learn LogisticRRerrsssinn implementation of logistic regression, with a tolerance value of tol=le-18 18 and an inverse regularization value of C=1e8. The maximum number of iterations is set 500. An intercept (i.e. bias) is not used for this fit.
To formally prove that the fraction of separable dichotomies is f(P,N) for standard periodic con- volutional layers, first note that the convolution is equivariant with respect to cyclic permutation of the inputs and of the outputs. The representation for cyclically permutating the output tensor can be written D ग where æ is the representation that cyclically permutes the entries of W x L matrices. Since each copy of contains one trivial irrep in its decomposition into direct sum of
18

---

Published as a conference paper at ICLR 2022
1.0
0.8
0..
0.4
conv block
block theory
0.2
maxpool
conv block
0.0
0.5
1.0
1.5
2.0
2.5
a P/No
Figure A.1: The fraction realizable dichotomies of non-periodic convolutional layers is higher than periodic convolutional layers, but still obeys the same scaling. Details exactly as in Fig- ure 2b, but using non-periodic convolutions with a zero padding of size 1. Here the theory line refers the theory for periodic convolutions.
irreps, the direct sum Di k== contains N trivial irreps in its decomposition. The final step to Theorem is to argue that the centroids of the manifolds are in general position. Since nonlinearity (ReLU) is applied to the output of the convolution, and since there is no particular structure in the convolutional filters beyond possibly sparsity, we can generically expect this to be the case.
A.4.2 LOCAL POOLING
First we prove an extension Lemma to equivariant linear maps. This will be used to show that average pooling does not affect the capacity of the regular representation of Zm-
Lemma 2. Let π be representation of the group G and suppose the matrix P is equivariant with respect the restriction of n. to a subgroup H C G, that for all h E H PT(h) -phh) ((h))P P for some representation of H. Let R denote a set of representatives of G/H. Then we have the following equivalence.
Fi Vu E [P],9 E y w PT(g)r" >0
Ew Vp [P] Ag' E " ((T(()))eHH(gg)) > 0.
Proof. For the forward implication, we write the coset decomposition = hgg of and average over H to find
Vg E G yd w PT(g)r" >0 wh E H.g R y (g(h) >0
Vgg E R: y"" P(T(h)))eHH(()))) O.
For the backward implication, suppose y " P(T(())) rr for all representatives g' e R, and define w Te For any 9 G, take coset decomposition hg for h E H and g' E R. We then have
" Pr(lgr" = y T PT(h))((g')) rm (Coset decomposition)
T p(h)PP(g rr (P H-equivariant)
w (p(h')) ( "r" (Definition of w)
w (p(hi))eH PT(g')r" (Invariance of measure)
y w TP (T(h)))e n (g'') rr (P is linear and H H-equivariant)
> O (By assumption).
(5)
The implication follows.
n
19

---

Published as a conference paper at ICLR 2022
Lemma 3. For the regular representation G Zp. local average pooling windows of size io generates a matrix P which is equivariant with respect to the subgroup H Zp/k with the property that
=
(6)
where a >> O is a positive constant.
Proof. First, note that the new pooled code is the regular representation of H since shifts of size mk the original feature map corresponds to shifts of length m in the pooled code. Thus P equivariant to H Zp/k- Next we note the following two facts
P ((((h))EE = =d' D P ((T(h)) = ==11;=11
(8)
a' and a" are positive constants and 1D and 1p/k are the D and D/k dimensional vector of all ones, respectively. Thus, we have that (* ( where a positive constant.
Theorem 2. The fraction of linearly separable dichotomies of a CNN pooling layer with N filters after average pooling from feature maps with the size of the input image W x L pooled feature maps of size W/k x L/k is f(P.N) i.e. no capacity is lost due to local average pooling.
Proof. The CNN layer before pooling is a regular representation æ of the full group G = Zw x Z applied to each of the M input channels via direct a sum + j=1 The layer after pooling is regular representation p of the subgroup H = Zw/k x ZLKk- also applied to the output channels via a direct sum 0/=11 P. Let R be set of representatives of G/ H.H. Since is equivariant to and p over H we have by the previous two lemmas that
Ag E G y T PP(lgr" > 0 Vg' E w P(T(())) > 0
((
Vgg E R: y" w P(T(a)) (g')r"
y"w w P(T(g)) >0
y" " P(a(t)))eHT" >0
y"w" T (p(h)))eH >0
Thus the capacity is determined by the rank of (p(h)))eET, assuming the (p(h)) ben Pr are in general position. Since each is a copy of the regular representation for H, the rank of (O)= p(N)) is merely N. Thus the fraction of linearly separable dichotomies is f(P, N), the same as the capacity before pooling.
Now prove local pooling operations in standard CNN preserve regular representation of subgroup the cyclic group.
Lemma 4. Suppose P is a local pooling operation on two-dimensional signals (CNN (CNNfeature maps), and that π is the regular representation of group G = Zw ZL on code a(x). A pooled feature map T = P(a) which acts on l windows of a is a regular representation of the subgroup H Zwik ZL,K-
Proof. Suppose an equivariant feature map a(x) E R RWXLXN has corresponding regular represen- tation of the group G Zw x Z₁ for each of the N filters. Consider any local pooling operation P (.) (such as average or maximum) which acts on ls x & patches where & divides both W and L.
rijuh = P (Lav (x())) / E (ik, (i + 1) E Lik; (j + 1)4{))
Note that for > 1. r(x) is no longer equivariant to since the representation does not satisfy the homomorphism property for shifts with length é not divisible by k. However, the code is cquivariant to a subgroup = Zw/k x Zt/kk namely vertical and horizontal shifts with length divisible by kt Let π mk. represent vertical shift of the image by nk pixels and horizontal shift
20

---

Published as a conference paper at ICLR 2022
by mk pixels. Note that aij. mx) h-th pooled feature map transforms as
ditnk.j+mk (x) since a(x) is equivariant. Then, the
Pija T m)) = P (far of M mx
1 (ik, (i 1) (f (1+1))))
= P (fay+nk Amkk (x)
[ik, (i 1)4J, e (
(a is Equivariant to x²)
P ((ay I E [[n + i)k; (n + i 1 E [(m + 5)k, (m + + 1)&{))
(k divides W, H)
-mm (2:)
(Definition r)
We thus find that the code regular representation of the subgroup of the cyclic translations
H {(nk, ( This new group G' has dimension H GG).
A.4.3 LOWER BOUND AND UPPER BOUND ON CAPACITY FOR NONLINEAR POOLING
Theorem 3. Suppose a code which is equivariant to a finite group G is pooled to new code which equivariant to a finite subgroup H S G. Suppose the number of trivial dimensions in the original G-equivariant code is No- Then the fraction of linearly separable dichotomies the G-invariant problem for the pooled code at least f(P, [No/k]) where k = =G//H) Similarly the fraction is at most (o)
Proof. The pooled code, by assumption, has the property P(x(hg')r) = p(h)P (T(g)(((())))) for any E H and g'= E R. where R set of representatives of G/H. The G-invariant separability condition amounts to the proposition
Bulk E (P)V) E H.S E y"w (())((())))))> >0
(10)
Fee E [P] E y= (p(h))neH P(T(g')m")) > 0:
(11)
in other words, a solution on the right hand side affords a solution over all of the manifolds generated in the input space. We see that, this requires considering if this particular dichotomy is linearly separble on the Pk anchor points (p(h))neн ((x(gg))r" )"") The simplest strategy to obtain an upper bound is to consider what happens when single new manifold is added. We that when single new base point r is added it corresponds to new points in the orbit (p) ((=(gg))r) for all g' R. Suppose that (p(h)) has rank Ng. Let C(P, No) represent the number of linearly separable dichotomies for P G-orbits in No trivial dimensions. Upon the addition of the k new points (P P + 1), we find that some of the pre-existing separable dichotomies give a new separable dichotomy. This can be guaranteed to occur when a w separates the old dichotomy and has w (p) (Pr(gg))r
for the new anchor point (but this condition is not necessary for a new dichotomy to be separable). This condition means that the original dichotomy is separable in the No- k dimensional subspace {w w ((T(g')r) 0}. By making infinitesimal adjustment to this w the correct label on this new orbit can be achieved without altering the labels on any other dichotomy. Since this argument gives sufficient but not necessary condition to generate a new dichotomy, obtain the following inequality
C( Z C(P,No) + CCP,No -)).
(12)
Solving this recursion gives the capacity PPotted (P, > Scover (P. [No/k]]. The greatest ca- pacity occurs in the special case where (p) ((T(g'))) theorem applies giving a fraction of separable dichotomies of (P,Noo) This is achieved, for in- stance in average pooling as we showed in Theorem 2.
(p) P(r). In this case, the usual counting
A.4.4 DIRECT SUM EQUIVARIANT CONVOLUTIONAL LAYERS
Here we describe how to build a convolutional layer architecture that is equivariant with respect to the regular representation in the input space and the direct sum representations introduced in Section 4.3 in the output space. For the following we assume that my and m2 are coprime, though the footnote in Section 4.3 for discussion of how to loosen this requirement.
The input data is a W x L x M tensor where M is the number of input channels. The first step is to simply take the output of standard convolution (in simulations also apply ReLU
21

---

Published as a conference paper at ICLR 2022
nonlinearity) applied to this imput with periodic boundary conditions, resulttin in W x X tensor where is the number output channels. The next step is to, for each of the output channels, take an average (or maximum) between entries spaced my entries apart horizontally or vertically in the matrix, resulting in an mi X my matrix. In our simulations we took averages rather than maximums. This is repeated for the other number ma, resulting in an mg x m2 matrix. This is repeated for every output channel, resulting in N matrices of size m. X my and N matrices of size m2 x m2. Finally, the resulting matrices are flattened and appended into an (mī + mž) N matrix, and the result is passed through nonlinearity (ReLU).
As the input tensor is cyclically permuted according to a regular representation т of Zmimz the output of this equivariant convolutional layer permutes according the representation x²1) + T (2) where (1)) is the regular representation of Zm, and x is the regular representation of Zmg-
The proof that the fraction of separable dichotomies is given by f(P, 2.) follows the same proof as for the standard periodic convolutions in Appendix A.4.1. Instead of a direct sum + k=1 πT we get direct sum + kー (f())r((()) (2)). Each of the π. (1)) contain two trivial irreps in its decomposition, so that the final fraction is ((P,2N)
N
A.4.5 INDUCED REPRESENTATIONS
First we state the definition of an induced representation. Let H be a subgroup of finite group G and let p : H + GL(WW be representation of H. Let V be the vector space of functions f: G + W such that [ghh f(g) for all h E H and E G. We now define the induced representation
+ GV) to be the representation which satisfies (T(g')f)(g) = f(gg').
For intuition. note that every element of can be written = rh where r is representative for coset in G/H and h H. This because the cosets G/ H partition G and the action of H stays within a coset; hence r selects out the coset, and h goes to the desired element of the coset: g = rh. With this decomposition, the action of π is then (r) = (gr). Hence the r component under has the effect of permuting to the new coset that gr belongs in, and the h component under ı then has the effect p(h) on the resulting vector [gr) that we originally specified. This is the most natural way get representation of G from representation of H. In the case of finite groups, one can think of the r component as permuting a set of isomorphic copies of V, each copy corresponding different coset.
To compute the capacity of induced representations, and so prove Proposition 1, we use Frobenius G GL.(V) is the map
reciprocity of characters. Recall that the character 0 of a representation 0: + C induced by the trace: 0(g) = (r(x(g)). Now let 0 be the character of p H + GL(V) and let 0 be the character of the induced representation. Then (0C (g)) = (0(h)) by Frobenius reciprocity of characters (Mackey, 1970). The average of the character is the number of trivial representations contained in the decomposition of the representation (see Serre (2014)). Hence the capacity of the induced representation is equal to the capacity of p. The existence of extensions beyond finite groups not clear to the authors, but we welcome information such exists.
22


Reviews:
[{"review_id": "cxpt2aNMyl", "reviewer": "Reviewer_s9Dq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "### Strengths\n- This paper contributes to an underexamind area, theoretical analysis of expressivity of equivariant neural networks.  In particular, there is a large gap between what we know for non-equivariant and equivariant models, and this papers helps to close that gap. \n- The definition of perceptron capacity for invariant models is logical and useful.\n- The result the authors obtain for the capacity of invariant models is simple and easy to compute.  This means it is easier to interpret and potentially useful. \n- I appreciate that operations such as pooling, which do not fit as nicely into the theory of equiv. NNs, but are still important, were considered.\n- The empirical evaluation is quite convincing, suggesting the theory is correct.\n- The related works section is actually a very nice and comprehensive survey of what (limited) theoretical work has been done on equivariant models. \n\n### Weakness\n- While I think it is important to examine the model capacity of equivariant models under the assumption of symmetrically distributed data, I’m not sure if perceptron capacity is the most relevant measure.  In some sense, this is evidenced by how simple the answer turns out to be depending only on the representation type of the final layer.  I wonder if other measures of capacity might be more relevant for understanding difference in model architecture?\n- I’m not sure how much section 4 adds.  The examples are essentially just computing the multiplicity of the trivial rep in some group representations.  This is fairly straightforward using the peter-weyl theorem or characters.  \n\n### Questions\n- What are the practical implications of the main theorem?   Is it better to add extra copies of the trivial representation to the final layer of the NN? \n- Would the analysis of local pooling also be relevant to strided convolutions? \n- If we assume the perceptron given by w is invariant, does this affect the result? (I guess not.)  \n\n\n### Small Notes\n- Some of the citations in section 3 are really to references, not to the authors of the results.  This is okay, but it should be clarified. \n- the definition of fixed point subspace does not need “largest”.  The definition is pointwise, so you can just define $W = \\lbrace w \\in V | g w = w \\text{ for all } g \\in G\\rbrace$.\n- Eqn 5 has no quantifier on h \n- I don’t understand the argument for the upper bound in 5.1.2.  In particular, i’m not sure what is meant by “limiting case” or the set of points is that are equal.  Can you clarify it for me? \n- 5.2: Should it be $\\rho : H \\to GL(V)$ since it acts on V?  \n- 5.2: It might be good to state a formal proposition here. \n\n\n", "summary_of_the_paper": "This paper addresses an underexamined area, the question of expressivity in equivariant neural networks.  In general, there is a large gap between our theoretical understanding of expressivity and generalization for non-equivariant networks and that for equivariant ones; this paper helps to close the gap.  In particular, given a set of equivariant representations coming from an equivariant architecture, the authors determine how expressive these features are for an invariant binary classification problem.  To do so, they define a reasonable generalization of perceptron capacity for invariant classifiers and compute it.  The answer turns out to be relatively simple and is mainly determined by the multiplicity of the trivial representation in the group representation type of the equivariant representation, which is not difficult to compute.  The authors also consider the case of useful but not quite equivariant operations such as pooling. Lastly, they provide a convincing empirical verification of their results.", "summary_of_the_review": "I tend towards accept due to the importance of making progress on what I see an underserved area.  However, I have some questions about the practical consequences of the work and whether other definitions of expressivity might have more potential. ", "strength_and_weaknesses": "", "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": {}}, {"review_id": "bInfj9kwJ8g", "reviewer": "Reviewer_zVT9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "*Strengths*\n\n** Fundamental problem: The paper studies a fundamental property of equivariant representations. To the best of my knowledge, their results are novel. The result is also quite elegant.\n\n** Good writing: The authors did a great job writing the paper. Specifically, the mathematical load is reduced by deferring details to the appendix, and many examples and illustrations are given. For this type of theoretical paper, the authors did a very good job.\n\n*Weaknesses*\n\n** Relevance to current research/challenges: I am not sure how this theoretical question is actually related to the current methods and challenges in geometric/equivariant deep learning, which uses non-linear models. I feel that section 5 is supposed to answer but I am not sure I am convinced. Another question: why is the separation of equivariant (rather than invariant) representations important? Most models use an invariant representation of the object, where (to the best of my understanding) the \\pi-manifold is trivial.\n\n\n", "summary_of_the_paper": "This is a mainly theoretical paper that studies the capacity of equivariant representations, which is, the ability to linearly classify objects under different transformations of a symmetry group of interest.\nThe main result in the paper is showing that the number of dichotomies (different binary classifications) is related to the dimension of the fixed subspace of the representations, rather than the dimension of the representation.\nThe authors discuss several examples and also propose several usages of this theory to deep learning of symmetric objects: analysis of pooling operations and induced representations\n", "summary_of_the_review": "The paper targets a fundamental problem regarding the separability of equivariant representations in a pretty general setup. The theoretical results are interesting and new (as far as I know), but the relevance to current research challenges is not clear. If this issue is addressed in a revision, I would be willing to upgrade my score.\n\nafter rebuttal:\nI appreciate the authors' thoughtful response. I will keep my score at 6 at this point.", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "YK0X8_puCCY", "reviewer": "Reviewer_hH77", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "**Strengths**:\n- The authors give a fantastic lemma which implies that classifying the $\\pi$-manifolds is equivalent to classifying their centroids.\n- The authors give some useful examples to help to understand. They then also compare the expressivity of some different representations.\n- The idea is novel. This paper gives a new perception of how to describe the expressivity of a representation.\n\n**Weaknesses**:\t\n- Some mentioned notations are not defined in the main text, even if they are in the main theorem. It brings some problems for understanding. I can not find the definitions of \"in general position\" and \"range\" in theorem 3.2. If there is a notation table, it may be easier for reading and understanding.\n- Theorem 3.2 is true only when the centroids are in general position. Since I can not find the mathematical definition of \"in general position\", I do not know whether this assumption is too strong.\n- The authors do not give further theoretical analysis about Eq. (1).\n- The authors propose an algorithm to classify the $\\pi$-manifolds and claim it is efficient. Although the algorithm seems efficient, the authors did not give any analysis about the time complexity.", "summary_of_the_paper": "This paper studies the expressivity of a representation constrained by group equivariance. The authors first use a classical notion of the perceptron capacity to offer a quantification of the expressivity. Then, an algorithm is designed to efficiently classify the $\\pi$-manifolds. Besides, the authors further apply the theoretical results to some practical examples and give bounds on the capacity when pooling operators exist.", "summary_of_the_review": "Overall, I vote for rejection. The idea is novel and interesting. However, I think this work lack sufficient theoretical and empirical analyses.\n\n-----\n\nThe authors have carefully addressed my concern. My score is thus raised to 6.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CiWL8_puZmk", "reviewer": "Reviewer_bab9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths:\n- The paper is well embedded in literature and the problem formulation is clear.\n- The presentation is clear (though some jargon could be better explained, see below).\n- The examples are helpful.\n- The paper is reproducible (see attached code).\n- The paoer us well written and intuitive.\n\nWeakness:\n- The presentation of the main idea could be better organized (see minor comments below).\n- The result is quite intuitive in hindsight, but when reading the paper I struggled with notions of averaging representations over G. I started working out what it meant and figured that for non-trivial irreps the average is zero (for compact groups at least). Then, only later on in the paper (page 6) it is indeed mentioned that his is the case. This kind of intuition would have been nice to receive early on since, if I understood correctly, this is at the core of the approach: it explains why it is all about the trivial irreps (all about the invariant subspaces).\n- I'm not fully sure about the relevance of the \"one-shot learning\" section 5.3. It seems to avoid the need to generate (augment?) the entire dataset/orbits from the reference points $r^\\mu$. However, since the capacity is determined by invariant subspaces, and one typically indeed designs G-CNNs that are at the final layer invariant, each point in the orbit will be mapped to the same representation anyway. Does the algorithm therefore solve an non-existing problem? (I'm probably misinterpreting here and would be happy to stand corrected if so)\n\nRegarding Jargon:\nIt would be nice to help readers that are new to these kind of analysis with a bit more intuition on some terminology.\n- E.g., it would have been nice to provide a definition of “dichotomy”, it took me a while to figure out what is precisely meant with it (still not fully sure). Is it just the dataset, pairs of equivalence classes + label. Or is it an instance of a possible dataset?\n- Hopefully the “fraction of linearly separable dichotomies” (top page 5) is then also clearer. \n- What is “a datapoint in general position”? (general position?)\n- Section 4.3. What does coprime mean?\n\nMinor points:\n- Section 4.3. What is idea behind the direct sum representations, isn’t this just considering the direct product of two groups that may as well be analyzed independently.\n- Typo last sentence 5.1.1. “dichotomies if” -> “dichotomies is”\n- I find Figure 2 hard to interpret, mainly because of the vertical axis being “capacity”. When saying things like “max pooling reduces capacity by a factor between ¼ and 1” I expect this factor to be apparent on the vertical axis, but it seems to refer to the bending point (at some alpha) where capacity dives below 0.5. I think the further this point is to the right, the more complex datasets the method could represent and it indeed reflects capacity in that sense. But then the vertical axis is confusing to me, shouldn’t this be the fraction f?\n- One of the conclusions is that pooling may reduce capacity. The subsequent sentence says “This quantification of expressivity could prove a valuable tool in building new G-CNNs…” In what sense is it valuable. Could you be more explicit about what possible implications does this have on NN design. \n\n\n\n", "summary_of_the_paper": "The paper provides an analysis of network capacity of group equivariant NNs. The analysis is based on determining the fraction of linearly separable dichotomies. It is found that this fraction is determined by the the number of trivial irreps that appear in the decomposition of the representations into irreps. I.e., the fraction is determined by the number of sub-spaces that are left-invariant by the group action. The paper is intuitive, well written, and theoretical results are confirmed by experiments.", "summary_of_the_review": "All in all the paper is a nice read and provides interesting insights. The paper is sound and the proofs are good to follow. I consider it a high quality submission that could, however, still be improved a bit in its presentation.", "strength_and_weaknesses": "", "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:

Meta-review: The authors' provide a discussion of Cover's Theorem in the setting of equivariance.  The reviewers consider the work well explained and interesting, especially after the revisions, and so I will vote to accept.
Decision: Accept (Poster)