summaries: 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. The 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. The 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  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. 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. 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.
abstractText: 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.
references.authors: Yaser S. Abu-Mostafa
references.title: Hints and the VC Dimension
references.venue: Neural Computation, 5(2):278–288,
references.authors: Yaser S Abu-Mostafa Malik Magdon-Ismail Hsuan-Tien Lin
references.title: Learning from data, volume 4. AMLBook
references.authors: Brandon Anderson Truong Son Hy Risi Kondor
references.title: Cormorant: Covariant molecular neural networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Calvin K. Yip John E. Burke K. Christopher Garcia Nick V. Grishin Paul D. Adams Randy J. Read David Baker
references.title: Accurate prediction of protein structures and interactions using a threetrack
references.authors: Eric B. Baum
references.title: On the capabilities of multilayer perceptrons
references.venue: J. Complex.,
references.authors: Erik J. Bekkers Maxime W. Lafarge Mitko Veta Koen A.J. Eppenhof Josien P.W. Pluim Remco Duits
references.title: Roto-translation covariant convolutional networks for medical image analysis
references.authors: Alexander Bogatskiy Brandon Anderson Marwah Roussi David Miller Risi Kondor
references.title: Lorentz group equivariant neural network for particle physics
references.venue: In International Conference on Machine Learning,
references.authors: Nicolas Brunel Vincent Hakim Philippe Isope Jean-Pierre Nadal Boris Barbour
references.title: Optimal information storage and the distribution of synaptic weights: perceptron versus purkinje
references.venue: cell. Neuron,
references.authors: Nicolas J.-B. Brunel
references.title: Is cortical connectivity optimized for storing information
references.venue: Nature Neuroscience,
references.authors: Julio Chapeton Tarec Fares Darin LaSota Armen Stepanyants
references.title: Efficient associative memory storage in cortical circuits of inhibitory and excitatory neurons
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Shuxiao Chen Edgar Dobriban Jane Lee
references.title: A group-theoretic framework for data augmentation
references.venue: Advances in Neural Information Processing Systems,
references.authors: SueYeon Chung Daniel D. Lee Haim Sompolinsky
references.title: Classification and Geometry of General Perceptual Manifolds
references.venue: Physical Review X,
references.authors: Taco Cohen Max Welling
references.title: Group equivariant convolutional networks
references.venue: In ICML,
references.authors: Taco Cohen Maurice Weiler Berkay Kicanaoglu Max Welling
references.title: Gauge equivariant convolutional networks and the icosahedral cnn
references.venue: In ICML,
references.authors: Taco S Cohen Mario Geiger Maurice Weiler
references.title: A general theory of equivariant CNNs on homogeneous spaces
references.venue: Advances in Neural Information Processing Systems,
references.authors: Uri Cohen SueYeon Chung Daniel D. Lee Haim Sompolinsky
references.title: Separability and geometry of object manifolds in deep neural networks
references.venue: Nature Communications,
references.authors: T. Cover
references.title: Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition
references.venue: IEEE Trans. Electron. Comput.,
references.authors: John Denker W. Gardner Hans Graf Donnie Henderson R. Howard W. Hubbard L.D. Jackel Henry Baird Isabelle Guyon
references.title: Neural network recognizer for hand-written zip code digits
references.venue: Advances in Neural Information Processing Systems,
references.authors: James J DiCarlo David D Cox
references.title: Untangling invariant object recognition
references.venue: Trends in cognitive sciences,
references.authors: Alexander S Ecker Fabian H Sinz Emmanouil Froudarakis Paul G Fahey Santiago A Cadena Edgar Y Walker Erick Cobos Jacob Reimer Andreas S Tolias Matthias Bethge
references.title: A rotation-equivariant convolutional neural network model of primary visual cortex
references.venue: arXiv preprint arXiv:1809.10504,
references.authors: Stephan Eismann Raphael J.L. Townshend Nathaniel Thomas Milind Jagota Bowen Jing Ron O. Dror
references.title: Hierarchical, rotation-equivariant neural networks to select structural models of protein complexes
references.venue: Proteins: Structure,
references.authors: Bryn Elesedy Sheheryar Zaidi
references.title: Provably strict generalisation benefit for equivariant models
references.venue: Proceedings of the 38th International Conference on Machine Learning,
references.authors: Carlos Esteves Christine Allen-Blanchette Ameesh Makadia Kostas Daniilidis
references.title: Learning so(3) equivariant representations with spherical cnns
references.venue: In ECCV,
references.authors: Marc Finzi Samuel Stanton Pavel Izmailov Andrew Gordon Wilson
references.title: Generalizing convolutional neural networks for equivariance to lie groups on arbitrary continuous data
references.venue: In ICML,
references.authors: Marc Finzi Max Welling Andrew Gordon Wilson
references.title: A practical method for constructing equivariant multilayer perceptrons for arbitrary matrix groups
references.venue: ArXiv, abs/2104.09459,
references.authors: Emmanouil Froudarakis Uri Cohen Maria Diamantaki Edgar Y Walker Jacob Reimer Philipp Berens Haim Sompolinsky Andreas S Tolias
references.title: Object manifold geometry across the mouse cortical visual hierarchy
references.venue: bioRxiv,
references.authors: William Fulton Joe Harris
references.title: Representation Theory: A First Course. Readings in Mathematics
references.authors: E. Gardner
references.title: Maximum storage capacity in neural networks
references.venue: EPL, 4:481–485,
references.authors: E. Gardner
references.title: The space of interactions in neural network models
references.venue: Journal of Physics A,
references.authors: Jonathan Gordon David Lopez-Paz Marco Baroni Diane Bouchacourt
references.title: Permutation equivariant models for compositional generalization in language
references.venue: In ICLR,
references.authors: Torkel Hafting Marianne Fyhn Sturla Molden May-Britt Moser Edvard I. Moser
references.title: Microstructure of a spatial map in the entorhinal
references.venue: cortex. Nature,
references.authors: Jason S. Hartford Devon R. Graham Kevin Leyton-Brown Siamak Ravanbakhsh
references.title: Deep models of interactions across sets
references.venue: In ICML,
references.authors: John Hertz Anders Krogh Richard G Palmer
references.title: Introduction to the theory of neural computation
references.authors: Guangbin Huang
references.title: Learning capability and storage capacity of two-hidden-layer feedforward networks
references.venue: IEEE transactions on neural networks,
references.authors: Nicolas Keriven Gabriel Peyré
references.title: Universal invariant and equivariant graph neural networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Johannes Klicpera Janek Groß Stephan Günnemann
references.title: Directional message passing for molecular graphs. ArXiv
references.authors: Risi Kondor Shubhendu Trivedi
references.title: On the generalization of equivariance and convolution in neural networks to the action of compact groups
references.authors: Risi Kondor Zhen Lin Shubhendu Trivedi
references.title: Clebsch-gordan nets: a fully fourier space spherical convolutional neural network
references.venue: In NeurIPS,
references.authors: Risi Kondor Hy Truong Son Horace Pan Brandon M. Anderson Shubhendu Trivedi
references.title: Covariant compositional networks for learning
references.venue: graphs. ArXiv,
references.authors: A. Kowalczyk
references.title: Estimates of storage capacity of multilayer perceptron with threshold logic hidden units
references.venue: Neural networks : the official journal of the International Neural Network Society,
references.authors: Alex Krizhevsky
references.title: Learning multiple layers of features from tiny images
references.venue: Technical report,
references.authors: Frederic Lanore N. Alex Cayco-Gajic Harsha Gurnani Diccon Coyle R. Angus Silver. Cerebellar granule cell axons support high-dimensional representations. Nature Neuroscience June
references.title: ISSN 1097-6256, 1546-1726
references.venue: doi: 10.1038/s41593-021-00873-x.
references.authors: Yann André LeCun Bernhard E. Boser John S. Denker Donnie Henderson Richard E. Howard Wayne E. Hubbard Lawrence D. Jackel
references.title: Backpropagation applied to handwritten zip code recognition
references.venue: Neural Computation,
references.authors: Richard L. Liboff
references.title: Primer for Point and Space Groups. Undergraduate Texts in Contemporary Physics
references.authors: Clare Lyle Mark van der Wilk Marta Z. Kwiatkowska Yarin Gal Benjamin Bloem-Reddy
references.title: On the benefits of invariance in neural networks. ArXiv
references.authors: George W. Mackey
references.title: Induced Representations of Locally Compact Groups and Applications, pp. 132–166
references.venue: ISBN 978-3-64248272-4
references.authors: Diego Marcos Benjamin Kellenberger Sylvain Lobry Devis Tuia
references.title: Scale equivariance in cnns with vector fields
references.venue: ArXiv,
references.authors: Haggai Maron Heli Ben-Hamu Nadav Shamir Yaron Lipman
references.title: Invariant and equivariant graph networks. ArXiv
references.authors: Haggai Maron Ethan Fetaya Nimrod Segol Yaron Lipman
references.title: On the universality of invariant networks
references.venue: In Proceedings of the 36th International Conference on Machine Learning,
references.authors: Haggai Maron Or Litany Gal Chechik Ethan Fetaya
references.title: On learning sets of symmetric elements
references.venue: ArXiv, abs/2002.08599,
references.authors: Mark Aronovich Naimark Aleksandr Isaakovich Stern
references.title: Theory of group representations, volume 246
references.authors: Mauro Pastore Pietro Rotondo Vittorio Erba Marco Gherardi
references.title: Statistical learning theory of structured data
references.venue: Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics,
references.authors: Cengiz Pehlevan Anirvan M. Sengupta
references.title: Resource-efficient perceptron has sparse synaptic weight distribution
references.venue: 25th Signal Processing and Communications Applications Conference (SIU),
references.authors: Nathanael Perraudin Michaël Defferrard Tomasz Kacprzak Raphael Sgier
references.title: Deepsphere: Efficient spherical convolutional neural network with healpix sampling for cosmological applications
references.venue: Astron. Comput.,
references.authors: Siamak Ravanbakhsh
references.title: Universal equivariant multilayer perceptrons
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: Mattia Rigotti Omri Barak Melissa R Warden Xiao-Jing Wang Nathaniel D Daw Earl K Miller Stefano Fusi
references.title: The importance of mixed selectivity in complex cognitive
references.venue: tasks. Nature,
references.authors: Pietro Rotondo Marco Cosentino Lagomarsino Marco Gherardi
references.title: Counting the learnable functions of geometrically structured data
references.venue: Physical Review Research,
references.authors: Ran Rubin L.F. Abbott Haim Sompolinsky
references.title: Balanced excitation and inhibition are required for high-capacity, noise-robust neuronal selectivity
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Akiyoshi Sannai M. Imaizumi M. Kawano
references.title: Improved generalization bounds of group invariant / equivariant deep networks via quotient feature spaces. 2019a
references.authors: Akiyoshi Sannai Yuuki Takai Matthieu Cordonnier
references.title: Universal approximations of permutation invariant/equivariant functions by deep neural networks
references.venue: ArXiv, abs/1903.01939,
references.authors: Victor Garcia Satorras E. Hoogeboom F. Fuchs I. Posner M. Welling
references.title: E(n) equivariant normalizing flows for molecule generation
references.venue: in 3d. ArXiv,
references.authors: Ludwig Schläfli
references.title: Theorie der vielfachen Kontinuität, pp. 167–387
references.venue: ISBN 978-3-0348-4118-4
references.authors: Bernhard Schölkopf Alexander J. Smola
references.title: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Adaptive Computation and Machine Learning
references.authors: Nimrod Segol Yaron Lipman
references.title: On universal equivariant set networks
references.venue: ArXiv, abs/1910.02421,
references.authors: Jean-Pierre Serre
references.title: Linear Representations of Finite Groups. Graduate Texts in Mathematics
references.authors: H Sebastian Seung Daniel D Lee
references.title: The manifold ways of perception
references.authors: John Shawe-Taylor
references.title: Threshold network learning in the presence of equivalences
references.venue: In NIPS,
references.authors: Mariya Shcherbina Brunello Tirozzi
references.title: Rigorous Solution of the Gardner Problem
references.venue: Communications in Mathematical Physics,
references.authors: N. Shutty Casimir Wierzynski
references.title: Learning irreducible representations of noncommutative lie groups
references.venue: ArXiv, abs/2006.00724,
references.authors: Karen Simonyan Andrew Zisserman
references.title: Very deep convolutional networks for large-scale image recognition
references.venue: CoRR, abs/1409.1556,
references.authors: Bart Smets Jim Portegies Erik J. Bekkers Remco Duits
references.title: Pde-based group equivariant convolutional neural networks. ArXiv
references.authors: Jure Sokolic Raja Giryes Guillermo Sapiro Miguel Rodrigues
references.title: Generalization Error of Invariant Classifiers
references.venue: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics,
references.authors: Eduardo Sontag
references.title: Shattering all sets of k points in general position requires (k 1)/2 parameters
references.venue: Neural Computation,
references.authors: I. Sosnovik A. Moskalev A. Smeulders
references.title: Scale equivariance improves siamese tracking
references.venue: IEEE Winter Conference on Applications of Computer Vision (WACV),
references.authors: Sameet Sreenivasan Ila Fiete
references.title: Grid cells generate an analog error-correcting code for singularly precise neural computation
references.venue: Nature Neuroscience,
references.authors: Raphael J.L. Townshend Stephan Eismann Andrew M. Watkins Ramya Rangan Maria Karelina Rhiju Das Ron O. Dror
references.title: Geometric deep learning of rna structure
references.authors: Vladimir N. Vapnik Alexey Y. Chervonenkis
references.title: On the uniform convergence of relative frequencies of events to their probabilities
references.venue: Dokl. Akad. Nauk.,
references.authors: Bastiaan S. Veeling Jasper Linmans Jim Winkens Taco Cohen Max Welling
references.title: Rotation equivariant cnns for digital pathology
references.venue: ArXiv,
references.authors: Roman Vershynin
references.title: Memory capacity of neural networks with threshold and rectified linear unit activations
references.venue: SIAM J. Math. Data Sci.,
references.authors: Maurice Weiler Gabriele Cesa
references.title: General e(2)-equivariant steerable cnns
references.venue: ArXiv, abs/1911.08251,
references.authors: Maurice Weiler Mario Geiger Max Welling Wouter Boomsma Taco Cohen
references.title: 3d steerable cnns: Learning rotationally equivariant features in volumetric data
references.venue: NeurIPS,
references.authors: Maurice Weiler Fred A. Hamprecht Martin Storath
references.title: Learning steerable filters for rotation equivariant cnns
references.venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Maurice Weiler Patrick Forr’e Erik P. Verlinde Max Welling
references.title: Coordinate independent convolutional networks - isometry and gauge equivariant convolutions on riemannian
references.venue: manifolds. ArXiv,
references.authors: J.G. Wendel
references.title: A problem in geometric probability
references.venue: Mathematica Scandinavica,
references.authors: Eugene Wigner
references.title: Gruppentheorie Und Ihre Anwendung Auf Die Quantenmechanik Der Atomspektren
references.venue: Vieweg+Teubner Verlag, Wiesbaden, first edition,
references.authors: Marysia Winkels Taco Cohen
references.title: Pulmonary nodule detection in ct scans with equivariant cnns
references.venue: Medical image analysis,
references.authors: Daniel E. Worrall Gabriel J. Brostow
references.title: Cubenet: Equivariance to 3d rotation and translation
references.venue: In ECCV,
references.authors: Daniel E. Worrall Stephan J. Garbin Daniyar Turmukhambetov Gabriel J. Brostow
references.title: Harmonic networks: Deep translation and rotation equivariance
references.venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Dmitry Yarotsky
references.title: Universal approximations of invariant maps by neural networks. ArXiv
references.authors: Chulhee Yun S. Sra A. Jadbabaie
references.title: Small relu networks are powerful memorizers: a tight analysis of memorization capacity
references.venue: NeurIPS,
sections.heading: 1 INTRODUCTION
sections.text: 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 are 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 et al., 1989; LeCun et al., 1989) and recently being generalized by the influential 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 transformations are seeing diverse and rapidly growing applications (Townshend et al., 2021; Baek 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 addition, equivariant CNNs have been shown to capture response properties of neurons in the primary visual cortex beyond classical Gábor filter models (Ecker et al., 2018).
  While it is clear that equivariance imposes a strong constraint on the geometry of representations and thus of perceptual manifolds (Seung & Lee, 2000; DiCarlo & Cox, 2007) that are carved out by these representations as the objects transform, the implications of such constraints on their expressivity 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 as 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-δ 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.
  Classical work on perceptron capacity focused on points in general position (Wendel, 1962; Cover, 1965; Schlä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 pooling layers, through theory and verify through simulation.
sections.heading: 1.1 RELATED WORKS
sections.text: Work most related to ours falls along two major axes. The first follows the classical perceptron capacity result on the linear separability of points (Schläfli, 1950; Wendel, 1962; Cover, 1965; Gardner, 1987; 1988). This result initiated a 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 it 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 et 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 architecture. In particular, the internal representations of a CNN are approximately1 translation equivariant: if the input image is translated by an amount t, 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 equivariance to more general transformation groups. This idea has been used to construct networks equivariant to a wide variety of transformations such as planar 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., 2018a; Kondor et al., 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 isometries (Weiler et al., 2018a; 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.
  A quite general theory of equivariant/invariant networks has also emerged. Kondor & Trivedi (2018) gave a complete description of GCNNs for scalar fields on homogeneous spaces of compact groups. This was generalized further to cover the steerable case in (Cohen et al., 2019b) and to general gauge fields in (Cohen et al., 2019a; Weiler et al., 2021). This theory also includes universal approximation results (Yarotsky, 2018; Keriven & Peyré, 2019; Sannai et al., 2019b; Maron et al., 2019b; Segol & Lipman, 2020; Ravanbakhsh, 2020). Nevertheless, while benefits of equivariance/invariance in
  1Some operations such as max pooling and boundary effects of the convolutions technically break strict equivariance, as well as the final densely connected layers.
  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). Abu-Mostafa (1993) made the argument that restricting a classifier to be invariant can not increase its VC dimension. Sokolic et al. (2017) extend this idea to derive generalization bounds for invariant classifiers, while Sannai et al. (2019a) do so specifically working with the permutation group. Elesedy & Zaidi (2021) show a strict generalization benefit for equivariant linear models, showing that the generalization gap between a least squares model and its equivariant version depends on the dimension of the space of anti-symmetric 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 on the limits to expressivity enforced by equivariance.
sections.heading: 2 PROBLEM FORMULATION
sections.text: Suppose x abstractly represents an object and let r(x) ∈ RN be some feature map of x to an N -dimensional space (such as an intermediate layer of a deep neural network). We consider transformations 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 g ∈ G as gx. Groups G may be represented by invertible matrices, which act on a 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(gx) = π(g)r(x),
  where π : G → GL(RN ) is a linear representation of G which acts on feature map r(x). Note that many representations of G are possible, including the trivial representation: π(g) = I 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 {π(g)rµ : g ∈ G} where µ ∈ [P ] ≡ {1, 2, . . . , P}; that is, these manifolds are orbits of the point rµ ≡ r(xµ) under the action of π. We will refer to such manifolds as π-manifolds.2
  Each of these π-manifolds represents a single object under the transformation encoded by π; hence, each of the points in a π-manifold is assigned the same class label. A perceptron endowed with a set of linear readout weights w will attempt to determine the correct class of every point in every manifold. The condition for realizing (i.e. linearly separating) the dichotomy {yµ}µ can be written as yµw>π(g)rµ > 0 for all g ∈ G and µ ∈ [P ], where yµ = +1 if the µth manifold belongs to the first class and yµ = −1 if the µth manifold belongs to the second class. The perceptron capacity is the fraction of dichotomies that can be linearly separated; that is, separated by a hyperplane.
  For concreteness, one might imagine that each of the rµ is the neural representation for an image of a dog (if yµ = +1) or of a cat (if yµ = −1). The action π(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 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 in Section 5.
sections.heading: 3 PERCEPTRON CAPACITY OF GROUP-GENERATED MANIFOLDS
sections.text: Here we first state and prove our results in the general case of representations of compact groups over RN . 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.
  3.1 SEPARABILITY OF π-MANIFOLDS We begin with a lemma which states that classifying the P π-manifolds can be reduced to the problem of classifying their P centroids. For the rest of Section 3, we let π : G → GL(RN ) be
  2Note that for a finite groupG, 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., 2019b); to be more mathematically precise, one could instead refer to these “manifolds” as π-orbits.
  an arbitrary linear representation of a compact group G.3 We denote the average of π over G with respect to the Haar measure by 〈π(g)〉g∈G; for finiteG this is simply 1|G| ∑ g∈G π(g) where |G| is the order (i.e. number of elements) of G. For ease of notation we will generally write 〈π〉 ≡ 〈π(g)〉g∈G when the group G being averaged over is clear.
  Lemma 1. A dataset {(π(g)rµ, yµ)}g∈G,µ∈[P ] consisting of P π-manifolds with labels yµ is linearly separable if and only if the dataset {(〈π〉rµ, yµ)}µ∈[P ] consisting of the P centroids 〈π〉rµ with the same labels is linearly separable. Formally,
  ∃w ∀g ∈ G,µ ∈ [P ] : yµw>π(g)rµ > 0 ⇐⇒ ∃w ∀µ ∈ [P ] : yµw>〈π〉rµ > 0.
  Proof. The forward implication is obvious: if there exists aw which linearly separates the P manifolds according to an assignment of 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 ∈ G. Since each of these quantities is positive, the average must be positive.
  For the reverse implication, suppose yµw>〈π〉rµ > 0, and define w̃ = 〈π〉>w. We will show that w̃ separates the P π-manfolds since
  yµw̃>π(g)rµ = yµw>〈π〉π(g)rµ (Definition of w̃) = yµw>〈π(g′)π(g)〉g′∈Grµ (Definition of 〈π〉 and linearity of π(g)) = yµw>〈π〉rµ (Invariance of the Haar Measure µ(Sg) = µ(S) for set S) > 0 (Assumption that w separates centroids)
  Thus, all that is required to show that w̃ separates the π-orbits are basic properties of a group representation and invariance of the Haar measure to G-transformations.
sections.heading: 3.2 RELATIONSHIP WITH COVER’S THEOREM AND VC DIMENSION
sections.text: The fraction f of linearly separable dichotomies on a dataset of size P for datapoints in general position 4 in N dimensions was computed by Cover (1965) and takes the form
  f(P,N) = 21−P N−1∑ k=0 ( P − 1 k ) (1)
  where we take ( n m ) = 0 for m > n. Taking α = P/N , f is a nonincreasing sigmoidal function of α that takes the value 1 when α ≤ 1, 1/2 when α = 2, and approaches 0 as α → ∞. In the thermodynamic limit of P,N → ∞ and α = O(1), f(α) converges to a step function f̄(α) = limP,N→∞,α=P/N f(P,N) = Θ(2 − α) (Gardner, 1987; 1988; Shcherbina & Tirozzi, 2003), indicating that in this limit all dichotomies are realized if α < 2 and no dichotomies can be realized if α > 2, making αc = 2 a critical point in this limit.
  The VC dimension (Vapnik & Chervonenkis, 1968) of the perceptron trained on points in dimension N is 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.5 Because f(P,N) = 1 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 f reveal that f(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/N0 where N0 is the dimension of the fixed point subspace (defined below). We are now ready to state and prove our main theorem.
  3Note that our results extend to more general vector spaces than RN , under the condition that the group be semi-simple.
  4A set of P points is in general position in N -space if every subset of N or fewer points is linearly independent. This says that the points are “generic” in the sense that there aren’t any prescribed special linear relationships between them beyond lying in anN -dimensional space. Points drawn from a Gaussian distribution with full-rank covariance are in general position with probability one.
  5This is because linear dependencies decrease the number of separable dichotomies (see Hertz et al. (2018)).
  Theorem 1. Suppose the points 〈π〉rµ for µ ∈ [P ] lie in general position in the subspace V0 = range(〈π〉) = {〈π〉x : x ∈ V }. Then V0 is the fixed point subspace of π, and the fraction of linearly separable dichotomies on the P π-manifolds {π(g)rµ : g ∈ G} is f(P,N0), where N0 = dimV0. Equivalently, N0 is the number of trivial irreducible representations that appear in the decomposition of π into irreducible representations.
  The fixed point subspace is the subspace W = {w ∈ V |gw = w ,∀g ∈ 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). A representation π : G → GL(V ) is irreducible if V is not 0 and if no vector subspace of V is stable under G, other than 0 and V (which are always stable under G). A subspace W being stable (or invariant) under G means that π(g)w ∈ W for all w ∈ W and g ∈ G. 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 〈π〉. 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 decomposition into a direct sum of irreps π ∼= πk1⊕πk2⊕...⊕πkM acting on vector space V = V1⊕V2⊕...VM , where ∼= denotes equality up to similarity transformation. The indices kj indicate the type of irrep corresponding to invariant subspace Vj . The fixed point subspace V0 is the direct sum of subspaces where trivial kj = 0 irreps act: V0 = ⊕ n:kn=0
  Vn. By the Grand Orthogonality Theorem of irreps (see Liboff (2004)) all non-trivial irreps average to zero 〈πk,ij(g)〉g∈G ∝ δk,0δi,j . Then, the matrix 〈π〉 simply projects the data to V0. By Lemma 1 the fraction of separable dichotomies on the πmanifolds is the same as that of their centroids 〈π〉rµ. Since, by assumption, the P points 〈π〉rµ lie in general position in V0, the fraction of separable dichotomies is f(P,dimV0) by Equation 1.
  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, N0 can be easily computed by averaging the trace of π, also known as the character, over G: N0 = 〈Tr(π(g))〉g∈G = Tr(〈π〉) (see Serre (2014)).
  Remark: If the perceptron readout has a bias term b i.e. the output of the perceptron isw>π(g)r+b, then this can be thought of as adding an invariant dimension. This is because the output can be written w̃>π̃(g)r̃ where w̃ = (w, b), r̃ = (r, 1), and π̃(g) = π(g) ⊕ 1 is π with an extra row and column added with a 1 in the last position and zeros everywhere else. Hence the fraction of separable dichotomies is f(P,N0 + 1).
  These results extend immediately to a notion of VC-dimension of group-invariant perceptrons.
  Corollary 1. Let the VC dimension for G-invariant perceptrons with representation π, NπV C , denote the maximum number P , such that there exist P anchor points {rµ}Pµ=1 so that {(π(g)rµ, yµ)}µ∈[P ],g∈G is separable for all possible binary dichotomies {yµ}µ∈[P ]. Then NπV C = dim(V0).
  Proof. By theorem 1 and Equation 1, all possible dichotomies are realizable for P ≤ dim(V0) provided the points 〈π〉 rµ are in general position.
  Our theory also extends immediately to subgroups. For example, strided convolutions are equivariant to subgroups of the regular representation.
  Corollary 2. A solution to the the G-invariant classification problem necessarily solves the G′invariant problem where G′ is a subgroup of G.
  Proof. Assume that yµw>r(gxµ) > 0 for g ∈ G. G′ ⊆ G =⇒ yµw>r(gxµ) > 0 ∀g ∈ G′.
  Consequently, the G′-invariant capacity is always higher than the capacity for the G-invariant classification problem.
  4 EXAMPLE APPLICATION: THE CYCLIC GROUP Zm In this section we illustrate the theory in the case of the cyclic group G = Zm on m elements. This group is isomorphic to the group of integers {0, 1, ...,m − 1} under addition modulo m, and this is the form of the group that we will consider. An example of this group acting on an object is an image that is shifted pixel-wise to the left and right, with periodic boundaries. In Appendix A.3 we show an application of our theory to the non-abelian Lie group SO(3).
sections.heading: 4.1 ROTATION MATRICES
sections.text: The 2 × 2 discrete rotation matrices R(θg) ≡ [ cos(θg) − sin(θg) sin(θg) cos(θg) ] where θg = 2πg/m and g ∈ Zm, are one possible representation of Zm; in this case V = R2. This representation is irreducible and nontrivial, which implies that the dimension of the fixed point subspace is 0 (only the origin is mapped to itself byR for all g). Hence the fraction of linearly separable dichotomies of the π-manifolds by Theorem 1 is f(P, 0). This result can be intuitively seen by plotting the orbits, as in Figure 1a for m = 4. Here it is apparent that it is impossible to linearly separate two or more manifolds with different class labels, and that the nontrivial irrepR averages to the zero matrix.
  The representation can be augmented by appending trivial irreps, defining π : G → GL(RN ) by π(g) = R(θg)⊕ I ≡ [ R(θg) 0
  0 I
  ] where I is an (N − 2)× (N − 2)-dimensional identity matrix.
  The number of trivial irreps is N − 2, so that the capacity is f(P,N − 2). This is illustrated in Figure 1b for the case N = 3. Here we can also see that the trivial irrep, which acts on the subspace span{(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 1 that dichotomies are realizable on the π-manifolds if and only if the dichotomies are realizable on the centroids of the manifolds.
  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 = Rm and π(g) is the matrix that cyclically shifts the entries of a length-m vector g places. For instance, if m = 3 and v = (1, 2, 3) then π(2)v = (2, 3, 1).
  In Appendix A.2 we derive the irreps of this representation, which consist of rotation matrices of different frequencies. There is one copy of the trivial irrep π0(g) ≡ 1 corresponding with the fixed point subspace span{1m}where 1m is the length-m all-ones vector. Hence the fraction of separable
  dichotomies is f(P, 1). This is illustrated in Figure 1c in the case where m = 3. The average of the regular representation matrix is 〈π〉 = 1|G|1m1 > m, indicating that 〈π〉 projects data along 1m.
sections.heading: 4.3 DIRECT SUMS OF REGULAR REPRESENTATIONS
sections.text: For our last example we define a representation using the isomorphism Zm ∼= Zm1 ⊕ Zm2 for m = m1m2 and m1 and m2 coprime6. Let π(1) : Zm1 → GL(Rm1) and π(2) : Zm2 → GL(Rm2) be the cyclic shift representations (i.e. the regular representations) of Zm1 and Zm2 , respectively. Consider the representation π(1)⊕π(2) : Zm → GL(Rm1+m2) defined by (π(1)⊕π(2))(g) ≡ π(1)(g mod m1)⊕π(2)(g mod m2), the block-diagonal matrix with π(1)(g mod m1) being the first and π(2)(g mod m2) the second block.
  There are two copies of the trivial representation in the decomposition of π(1) ⊕ π(2), corresponding to the one-dimensional subspaces span{(1m1 ,0m2)} and span{(0m1 ,1m2)}, where 0m1 is the length-k vector of all zeros. Hence the fraction of separable dichotomies is f(P, 2). This reasoning extends simply to direct sums of arbitrary length `, yielding a fraction of f(P, `).7 These representations 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 et al., 2005), which have desirable qualities in comparison to place cell representations (Sreenivasan & Fiete, 2011).8 Precisely, a collection {Zmk×Zmk}k of grid cell modules encodes a large 2-dimensional spatial domain Zm × Zm where m = ∏ kmk.
sections.heading: 5 G-EQUIVARIANT NEURAL NETWORKS
sections.text: The proposed theory can shed light on the feature spaces induced by G-CNNs. Consider a single convolutional layer feature map for a finite9 group G with the following activation
  ai,k(x) = φ(w > i g −1 k x) , gk ∈ G , i ∈ {1, ..., N} (2)
  for some nonlinear function φ. For each filter i, and under certain choices of π, the feature map ai(x) ∈ R|G| exhibits the equivariance property ai(gkx) = π(gk)ai(x). We will let a(x) ∈ R|G|N denote a flattened vector for this feature map.
  In a traditional periodic convolutional layer applied to inputs of width W and length L, the feature map of a single filter ai(x) ∈ R|G| is equivariant with the regular representation of the group G = ZW×ZL (the representation that cyclically shifts the entries ofW×Lmatrices). Here the order of the group is |G| = WL. Crucially, our theory shows that this representation contributes exactly one trivial irrep per filter (see Appendix A.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 1 shows that for G-invariant classification, only the trivial irreps contribute to 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 f(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 (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.1 and Figure A.1 for more information and the result of using non-periodic convolutions, which impact the capacity but not the overall scaling with N0.
  6Two numbers are coprime if they have no common prime factor. 7Our results do not actually require that the mk be coprime, but rather that none of the mk divide one of the others. To see this, take m̃ and m̃k, to be m and the mk after being divided by all divisors common among them. Then Zm̃ ∼= ⊕`k=1Zm̃k and provided none of the m̃k are 1, one still gets a fraction of f(P, `).
  8Place cells are analogous to standard convolutional layers. 9We consider finite groups here for simplicity, but the theory extends to compact Lie groups.
  Other GCNN architectures can have different capacities. For instance, a convolutional layer equivariant to the direct sum representation of Section 4.3 has double the capacity with P ∼ 4N (Figure 2c), since each output channel contributes two trivial irreps. See Appendix A.4.4 for an explicit construction of such a convolutional layer and a derivation of the capacity.
sections.heading: 5.1 POOLING OPERATIONS
sections.text: 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 P(r) : RN → RN/k be a pooling operation which reduces the dimension of the feature map. The condition that a given dichotomy {yµ} is linearly separable on a pooled code is
  ∃w ∈ RN/k ∀µ ∈ [P ], g ∈ G : yµw>P(π(g)rµ) > 0 (3)
  We will first analyze the capacity when P(·) is a linear function (average pooling) before studying the more general case of local non-linear pooling on one and two-dimensional signals.
sections.heading: 5.1.1 LOCAL AVERAGE POOLING
sections.text: 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 an argument similar to Lemma 1 (Lemma 2 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 a 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 f(P,N).
sections.heading: 5.1.2 LOCAL NONLINEAR POOLING
sections.text: Often, nonlinear pooling operations are applied to downsample feature maps. For concreteness, we 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) ∈ RN×D represent a 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/k for some integer k. Note that the pooled code is equivariant to the subgroup H = ZD/k, in the sense that P(π(h)r) = ρ(h)P(r) for any h ∈ 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 ∈ Zk and h ∈ ZD/k. The condition that a vector w separates the dataset is
  ∀µ ∈ [P ], j ∈ Zk, h ∈ H : yµw>ρ(h)P (π(j)rµ) > 0. (4)
  We see that there are effectively k points belonging to each of the P orbits in the pooled code. Since P (·) is nonlinear, the averaging trick utilized in Lemma 1 is no longer available. However, we can obtain a lower bound on the capacity, f(P, bN/kc), from a simple extension of Cover’s original proof technique as we show in Appendix A.4.3. Alternatively, an upper bound f ≤ f(P,N) persists since a w which satisfies Equation 4 must separate 〈ρ(h)〉h∈H P(rµ). This upper bound is tight when all k points 〈ρ(h)〉h∈H P(π(j)rµ) coincide for each µ, giving capacity f(P,N). 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 H-invariant capacity problem, the fraction of separable dichotomies is f(P,N), since ρ is a regular representation of H as we show in 4.
sections.heading: 5.1.3 GLOBAL POOLING
sections.text: Lemma 1 shows that linear separability of π-manifolds is equivalent to linear separability after global average pooling (i.e. averaging the representation over the group). This is relevant to 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 is efficient: Lemma 1 implies that it allows the learning of optimal linear readout weights following the pooling operation, given only a single point from each π-manifold (i.e. no need for data augmentation). Global average pooling reduces the problem of linearly classifying |G|P points in a space of dimension N to that of linearly classifying P points in a space of dimension dimV0. Note that by an argument similar to Section 5.1.2, global max pooling may in contrast reduce capacity.
sections.heading: 5.2 INDUCED REPRESENTATIONS
sections.text: Induced representations are a fundamental ingredient in the construction of general equivariant neural 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.
  Proposition 1. Let π be a representation of a finite group induced from ρ. Then the fraction of separable dichotomies of π-manifolds is equal to that of the ρ-manifolds.
sections.heading: 6 DISCUSSION AND CONCLUSION
sections.text: Equivariance has emerged as a powerful framework to build and understand representations that reflect 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 capacity. 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 of output channels in standard CNN layers, a fact we illustrate in simulations. However, our results are also very general, extending to virtually any equivariant representation of practical interest – in particular, they are immediately applicable to GCNNs built around more general equivariance relations, as we illustrate with an example of a GCNN equivariant to direct sum representations. We also calculate the capacity of induced representations, a standard tool in 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.
  While the concept of perceptron capacity has played an essential role in the development of machine learning systems (Schölkopf & Smola, 2002; Cohen et al., 2020) and the understanding of biological 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 et al., 2020), more work is wanting in linking it to other computational attributes of interest such as generalization. A comprehensive picture of 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)).
sections.heading: REPRODUCIBILITY STATEMENT
sections.text: Code for the simulations is attached as supplementary material zip file. This code includes an environment.yml file that can be used to create a 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-contained with the essential proofs, proofs of additional results and further discussion can be found in the Appendices below. These include
  Appendix A.1 a glossary of definitions and notation. Appendix A.2 a derivation of the irreps for the regular representation of the cyclic group Zm. 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 of 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.1.
sections.heading: A APPENDIX
sections.heading: A.1 NOTATION AND GLOSSARY
sections.text: • x: an abstract notation for an input object
  • r(x): a feature map of the input to an N dimensional vector space.
  • π: N dimensional linear representation of group G. For each g ∈ G, π(g) ∈ GL(RN ) is an N ×N invertible real matrix.
  • Equivariance property: r(gx) = π(g)r(x) for all g ∈ G and all x. • Invariant measure: a measure µ : G → R+ on G with µ(gS) = µ(S) = µ(Sg). For
  finite groups, the uniform distribution. For locally compact topological groups, the Haar measure.
  • 〈·〉g∈G: an average over the invariant measure of G • Irreducible representation (irrep): an irreducible representation ρ on vector space V satis-
  fies ρ(g)v ∈ V for all v ∈ V, g ∈ G. • Character χ(g): the trace of the representation χ(g) = Tr π(g).
  • Fixed point subspace: the subspace V0 for which π(g)v ∈ V0 for all v ∈ V0. • General position: a collection of P points in general position in an N dimensional vector
  space have the property that any subset of k ≤ 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 {yµ} of P points {xµ}. • f(P,N): 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 αc = P/N where P points in general position can be linearly separated by a N dimensional perceptron with probability 1 in an asymptotic limit where P,N → ∞ with P/N = ON,P (1). The classical result is αc = 2 (Gardner, 1987; Shcherbina & Tirozzi, 2003).
  • P(·): a local pooling operation.
  A.2 IRREPS FOR THE CYCLIC GROUP
  Here we compute the irreps of representations π : Zm → GL(V ) of the cyclic group Zm over a real vector space V (see (Serre, 2014) for a derivation of the irreps when V is a complex vector space). To find the irreps, one can use the form for the eigenvalues and eigenvectors for circulant matrices, since all the π(g) are circulant. This results in the simultaneous diagonalization π(g) = V (1⊕R(2πg/m)⊕R(4πg/m)⊕ · · · ⊕R((m− 1)πg/m))V > where V is the realvalued version of the discrete Fourier transform matrix (the columns are proportional to cosines and sines of varying frequencies, along with a column proportional to 1m).
  Note that the 2x2 rotation matrices R(2πgk/m) are irreps for k 6= m/2 and k 6= 0, since there is no one-dimensional subspace of R2 that is invariant to R(2πgk/m) for all g. The exception for k = m/2 if m is even, gives R(2πgk/m) = (−1)gI , which corresponds to rotation of 180 degrees. The subspace span{(1, 0)} is invariant to this action, so that R(2πgk/m) is not an irrep. This representation can thus be reduced to an action on a one-dimensional subspace, represented by (−1)g . The case k = 0 gives the trivial representation.
sections.heading: A.3 SO(3): A NON-ABELIAN LIE GROUP
sections.text: The special orthogonal group SO(3) on 3 dimensions (rotation group), the 3 × 3 orthogonal matrices with determinant +1, can also be analyzed within our theory. G-convolutional neural networks that are equivariant to SO(3) rotations have become of high interest in the physical sciences and computer vision where the objects of interest often respect these symmetries (Anderson et al.,
  2019; Cohen et al., 2018; Esteves et al., 2018; Kondor et al., 2018a) The irreducible representations have the form Bkm where Bkm are (2km + 1) × (2km + 1) block matrices, known as Wigner Dmatrices (Wigner, 1931). The trivial irreps correspond to the one-dimensional irreps with k = 0. Thus, the SO(3)-invariant classification capacity merely counts the number of trivial irreps which have N0 = ∑ m δkm,0. The capacity is again f(P,N0).
sections.heading: A.4 G-EQUIVARIANT CONVOLUTIONAL LAYERS
sections.heading: A.4.1 STANDARD CONVOLUTIONAL LAYERS
sections.text: A convolutional layer consists of a set of N k × k′ filters Fi that are convolved (technically crosscorrelated) with a stack of M W × 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 to the end of the padded image. Another possible choice is to loop the edges of the input tensor together, so that the filter is applied to the other side of the input tensor as it 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/N0 scaling of the periodic convolutions (Figure A.1).
  For the random convolutional layers of Figure 2a, the input tensors are size 10× 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 0. The filters are also of size 10 × 10 with periodic boundary conditions, and are initialized according to a 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=“circular” 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 general 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×2 max pooling layer (orange line in Figure 2a), provided by Pytorch 1.9’s MaxPool2d. The pretrained VGG-11 layers used in Figure 2b and Figure A.1 are taken from liukuang (2017). The first convolutional block (blue line) consists of 3 × 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 × 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 convolutions are set to be periodic in Figure 2b and nonperiodic with a zero padding sizes of 1 in Figure A.1, and the bias term is set to zero. The batch normalization is an element-wise operation and so equivariant 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× 2 max pooling layer (orange line). Finally, another convolutional block of 3 × 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 LogisticRegression implementation of logistic regression, with a tolerance value of tol=1e-18 and an inverse regularization value of C=1e8. The maximum number of iterations is set to 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 convolutional 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 ⊕N k=1 π where π is the representation that cyclically permutes the entries of W × L matrices. Since each copy of π contains one trivial irrep in its decomposition into a direct sum of
  irreps, the direct sum ⊕N
  k=1 π contains N trivial irreps in its decomposition. The final step to use Theorem 1 is to argue that the centroids of the manifolds are in general position. Since a 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.
sections.heading: A.4.2 LOCAL POOLING
sections.text: First we prove an extension of Lemma 1 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 a representation of the group G and suppose the matrix P is equivariant with respect to the restriction of π to a subgroupH ⊆ G, so that for all h ∈ H Pπ(h) = ρ(h)P for some representation ρ of H . Let R denote a set of representatives of G/H . Then we have the following equivalence.
  ∃w ∀µ ∈ [P ], g ∈ G : yµw>Pπ(g)rµ > 0 ⇐⇒ ∃w ∀µ ∈ [P ] ∀g′ ∈ R : yµw>P 〈π(h)〉h∈Hπ(g′)rµ > 0.
  Proof. For the forward implication, we write the coset decomposition g = hg′ of g and average over H to find
  ∀g ∈ G : yµw>Pπ(g)rµ > 0 ⇐⇒ ∀h ∈ H, g′ ∈ R : yµw>Pπ(h)π(g′)rµ > 0 =⇒ ∀g′ ∈ R : yµw>P 〈π(h)〉h∈Hπ(g′)rµ > 0.
  For the backward implication, suppose yµw>P 〈π(h)〉h∈Hπ(g′)rµ > 0 for all representatives g′ ∈ R, and define w̃ = 〈ρ(h)〉>h∈Hw. For any g ∈ G, take a coset decomposition g = hg′ for h ∈ H and g′ ∈ R. We then have
  yµw̃>Pπ(g)rµ = yµw̃>Pπ(h)π(g′)rµ (Coset decomposition)
  = yµw̃>ρ(h)Pπ(g′)rµ (P is H-equivariant)
  = yµw> 〈ρ(h′)〉h′∈H ρ(h)Pπ(g ′)rµ (Definition of w̃) = yµw> 〈ρ(h)〉h∈H Pπ(g ′)rµ (Invariance of measure) = yµw>P 〈π(h)〉h∈H π(g ′)rµ (P is linear and H-equivariant)
  > 0 (By assumption). (5)
  The implication follows.
  Lemma 3. For the regular representation of G = ZD, a local average pooling over windows of size k generates a matrix P which is equivariant with respect to the subgroup H = ZD/k with the property that
  P 〈π(h)〉h∈H = aP 〈π(g)〉g∈G (6)
  where a > 0 is a positive constant.
  Proof. First, note that the new pooled code is the regular representation of H since shifts of size mk in the original feature map corresponds to shifts of length m in the pooled code. Thus P is equivariant to H = ZD/k. Next we note the following two facts
  P 〈π(h)〉h∈H = a ′1D/k1 > D (7) P 〈π(h)〉g∈G = a ′′1D/k1 > D (8)
  a′ and a′′ are positive constants and 1D and 1D/k are theD andD/k dimensional vector of all ones, respectively. Thus, we have that P 〈π(h)〉h∈H = aP 〈π(g)〉g∈G where a is 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 × L to pooled feature maps of size W/k × 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 ×ZL, applied to each of the M input channels via a direct a sum ⊕M j=1 π. The layer after pooling is a regular representation ρ of the subgroup H = ZW/k×ZL/k, also applied to the output channels via a direct sum ⊕N j=1 ρ. Let R be a set of representatives of G/H . Since P is equivariant to π and ρ over H we have by the previous two lemmas that
  ∀g ∈ G : yµw>Pπ(g)rµ > 0 ⇐⇒ ∀g′ ∈ R : yµw>P 〈π(h)〉h∈Hπ(g′)rµ > 0 ⇐⇒ ∀g′ ∈ R : yµw>P 〈π(g)〉g∈Gπ(g′)rµ > 0 ⇐⇒ yµw>P 〈π(g)〉g∈Grµ > 0 ⇐⇒ yµw>P 〈π(h)〉h∈Hrµ > 0 ⇐⇒ yµw>〈ρ(h)〉h∈HPrµ > 0
  Thus the capacity is determined by the rank of 〈ρ(h)〉h∈H , assuming the 〈ρ(h)〉h∈HPrµ are in general position. Since each ρ is a copy of the regular representation for H , the rank of 〈 ⊕N
  j=1 ρ(h)〉h∈H is merely N . Thus the fraction of linearly separable dichotomies is f(P,N), the same as the capacity before pooling.
  Now we prove local pooling operations in a standard CNN preserve a regular representation of a subgroup of the cyclic group.
  Lemma 4. Suppose P is a local pooling operation on two-dimensional signals (CNN feature maps), and that π is the regular representation of a group G = ZW × ZL on code a(x). A pooled feature map r = P(a) which acts on k × k windows of a is a regular representation of the subgroup H = ZW/k × ZL/k.
  Proof. Suppose an equivariant feature map a(x) ∈ RW×L×N has corresponding regular representation of the group G = ZW × ZL for each of the N filters. Consider any local pooling operation P (·) (such as average or maximum) which acts on k × k patches where k divides both W and L.
  rij,h(x) = P ({ai′,j′,h(x) | i′ ∈ [ik, (i+ 1)k], j′ ∈ [jk, (j + 1)k]}) (9)
  Note that for k > 1, r(x) is no longer equivariant to G since the representation does not satisfy the homomorphism property for shifts with length ` not divisible by k. However, the new code is equivariant to a subgroup H = ZW/k × ZL/k, namely vertical and horizontal shifts with length divisible by k. Let πxnk,mk represent a vertical shift of the image x by nk pixels and horizontal shift
  by mk pixels. Note that aij,h(πxnk,mkx) = ai+nk,j+mk(x) since a(x) is equivariant. Then, the h-th pooled feature map transforms as
  rij,h(π x nk,mkx) = P ( {ai′,j′,h(πxnk,mkx) | i′ ∈ [ik, (i+ 1)k], j′ ∈ [jk, (j + 1)k]} ) = P ({ai′+nk,j′+mk,h(x) | i′ ∈ [ik, (i+ 1)k], j′ ∈ [jk, (j + 1)k]})
  (a is Equivariant to πx)
  = P ({ai′,j′,h(x) | i′ ∈ [(n+ i)k, (n+ i+ 1)k], j′ ∈ [(m+ j)k, (m+ j + 1)k]}) , (k divides W,H)
  = ri+n,j+m,h(x) , (Definition of r)
  We thus find that the code is a regular representation of the subgroup of the cyclic translations H = {(nk,mk)}n∈[H/k],m∈[W/k]. This new group G′ has dimension |H| = 1k2 |G|.
sections.heading: A.4.3 LOWER BOUND AND UPPER BOUND ON CAPACITY FOR NONLINEAR POOLING
sections.text: Theorem 3. Suppose a code which is equivariant to a finite group G is pooled to a new code which is equivariant to a finite subgroup H ⊆ G. Suppose the number of trivial dimensions in the original G-equivariant code is N0. Then the fraction of linearly separable dichotomies on the G-invariant problem for the pooled code is at least f(P, bN0/kc) where k = |G/H|. Similarly the fraction is at most f(P,N0).
  Proof. The pooled code, by assumption, has the property P(π(hg′)r) = ρ(h)P (π(g′)r) for any h ∈ H and g′ ∈ R, where R is a set of representatives of G/H . The G-invariant separability condition amounts to the proposition
  ∃w∀µ ∈ [P ] ∀h ∈ H, g′ ∈ R : yµw>ρ(h)P(π(g′)rµ) > 0 (10) ⇐⇒ ∃w∀µ ∈ [P ] ∀g′ ∈ R : yµw> 〈ρ(h)〉h∈H P(π(g ′)rµ) > 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 〈ρ(h)〉h∈H P(π(g′)rµ). The simplest strategy to obtain an upper bound is to consider what happens when a single new manifold is added. We see that when a single new base point r is added it corresponds to k new points in the orbit 〈ρ〉 P(π(g′)r) for all g′ ∈ R. Suppose that 〈ρ(h)〉h∈H has rank N0. Let C(P,N0) represent the number of linearly separable dichotomies for P G-orbits in N0 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(π(g′)r) = 0 for the new anchor point r (but this condition is not necessary for a new dichotomy to be separable). This condition means that the original dichotomy is separable in the N0 − k dimensional subspace {w : w · P(π(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 a sufficient but not necessary condition to generate a new dichotomy, we obtain the following inequality
  C(P + 1, N0) ≥ C(P,N0) + C(P,N0 − k). (12)
  Solving this recursion gives the capacity fPooled(P,N0) ≥ fCover(P, bN0/kc). The greatest capacity occurs in the special case where 〈ρ〉 P(π(g′)r) = 〈ρ〉 P(r). In this case, the usual counting theorem applies giving a fraction of separable dichotomies of f(P,N0). This is achieved, for instance in average pooling as we showed in Theorem 2.
sections.heading: A.4.4 DIRECT SUM EQUIVARIANT CONVOLUTIONAL LAYERS
sections.text: 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 m1 and m2 are coprime, though see the footnote in Section 4.3 for a discussion of how to loosen this requirement.
  The input data is a W × L ×M tensor where M is the number of input channels. The first step is to simply take the output of a standard convolution (in our simulations we also apply a ReLU
  nonlinearity) applied to this input with periodic boundary conditions, resulting in aW×L×N tensor where N is the number of output channels. The next step is to, for each of the output channels, take an average (or maximum) between entries spaced m1 entries apart horizontally or vertically in the matrix, resulting in anm1×m1 matrix. In our simulations we took averages rather than maximums. This is repeated for the other numberm2, resulting in anm2×m2 matrix. This is repeated for every output channel, resulting in N matrices of size m1 ×m1 and N matrices of size m2 ×m2. Finally, the resulting matrices are flattened and appended into an (m21 + m 2 2) × N matrix, and the result is passed through a nonlinearity (ReLU).
  As the input tensor is cyclically permuted according to a regular representation π of Zm1m2 , the output of this equivariant convolutional layer permutes according to the representation π(1) ⊕ π(2) where π(1) is the regular representation of Zm1 and π (2) is the regular representation of Zm2 .
  The proof that the fraction of separable dichotomies is given by f(P, 2N) follows the same proof as for the standard periodic convolutions in Appendix A.4.1. Instead of a direct sum ⊕N k=1 π we get a
  direct sum ⊕N
  k=1(π (1)⊕π(2)). Each of the π(1)⊕π(2) contain two trivial irreps in its decomposition,
  so that the final fraction is f(P, 2N).
  A.4.5 INDUCED REPRESENTATIONS
  First we state the definition of an induced representation. Let H be a subgroup of a finite group G and let ρ : H → GL(W ) be a representation of H . Let V be the vector space of functions f : G → W such that f(gh) = ρ(h)f(g) for all h ∈ H and g ∈ G. We now define the induced representation π : G→ GL(V ) to be the representation which satisfies (π(g′)f)(g) = f(gg′). For intuition, note that every element of g can be written g = rh where r is a representative for a coset in G/H and h ∈ H . This is 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 π(rh)f(g) = ρ(h)f(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 ρ(h) on the resulting vector f(gr) that we originally specified. This is the most natural way to get a representation of G from a 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 to a different coset.
  To compute the capacity of induced representations, and so prove Proposition 1, we use Frobenius reciprocity of characters. Recall that the character θ of a representation π : G→ GL(V ) is the map θ : G→ C induced by the trace: θ(g) = Tr(π(g)). Now let θ be the character of ρ : H → GL(V ) and let θG be the character of the induced representation. Then 〈θG(g)〉g∈G = 〈θ(h)〉h∈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 ρ. The existence of extensions beyond finite groups is not clear to the authors, but we welcome information if such exists.