Conjugation Invariant Learning with Neural Networks
Authors: Aaron Yi Rui Low
Subhroshekhar Ghosh
Yong Sheng Soh
Venue: ICLR 2022 Submitted (2022)
Keywords: Learning under group actions
Neural networks
Group representations
Characters
Class functions

Abstract: Machine learning under the constraint of symmetries, given by group invariances or equivariances, has emerged as a topic of active interest in recent years. Natural settings for such applications include the multi-reference alignment and cryo electron microscopy, multi-object tracking, spherical images, and so on. A fundamental paradigm among such symmetries is the action of a group by symmetries, which often pertains to change of basis or relabelling of objects in pure and applied mathematics. Thus, a naturally significant class of functions consists of those that are intrinsic to the problem, in the sense of being independent of such base change or relabelling; in other words invariant under the conjugation action by a group. In this work, we investigate such functions, known as class functions, leveraging tools from group representation theory. A fundamental ingredient in our approach are given by the so-called irreducible characters of the group, which are canonical tracial class functions related to its irreducible representations. Such functions form an orthogonal basis for the class functions, extending ideas from Fourier analysis to this domain, and accord a very explicit structure. Exploiting a tensorial structure on representations, which translates into a multiplicative algebra structure for  irreducible characters,  we propose to efficiently approximate class functions using polynomials in a small number of such characters. Thus, our approach provides a global, non-linear coordinate system to describe functions on the group that is intrinsic in nature, in the sense that it is independent of local charts, and can be easily computed in concrete models.  We demonstrate that such non-linear approximation using a small dictionary can be effectively implemented using a deep neural network paradigm. This allows us to learn a class function efficiently from a dataset of its outputs.

Under review as a conference paper at ICLR 2022
CONJUGATION INVARIANT LEARNING WITH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Machine learning under the constraint symmetries, given by group invariances or equivariances, has emerged as a topic of active interest in recent years. Natural settings for such applications include the multi-reference alignment and cryo elec- tron microscopy, multi-object tracking, spherical images, and so on. A fundamental paradigm among such symmetries the action of group by symmetries, which often pertains to change of basis relabelling of objects in pure and applied mathematics. Thus, a naturally significant class of functions consists of those that are intrinsic to the problem, in the sense of being independent of such base change or relabelling; in other words invariant under the conjugation action by a group. In this work, we investigate such functions, known as class functions, leveraging tools from group representation theory. A fundamental ingredient in our approach are given by the so-called irreducible characters of the group, which are canonical tracial class functions related to its irreducible representations. Such functions form an orthogonal basis for the class functions, extending ideas from Fourier analysis to this domain, and accord very explicit structure. Exploiting tensorial structure on representations, which translates into a multiplicative algebra structure for irreducible characters, we propose to efficiently approximate class functions using polynomials in a small number of such characters. Thus, our approach provides global, non-linear coordinate system to describe functions the group that is intrinsic in nature, in the sense that is independent of local charts, and be easily computed in concrete models. We demonstrate that such non-linean approximation using a small dictionary can be effectively implemented using a deep neural network paradigm. This allows to learn class function efficiently from a dataset of its outputs.
INTRODUCTION
Learning under group actions. Learning under group actions has emerged as a topic of key interest in recent years. The natural motivation for this paradigm comes from the many applications which there is canonical action of group of symmetries, often arising isometries or invariances of the model under consideration (Tebara & Kondor 2008 Wein 2018).
Instances of learning models that admit natural group actions manifold. Examples range from
natural image data that exhibit symmetries accorded by rotations and translations (Kondor 2007
Kakarala 2012): data arising in tomography (Vasco 2007 Moroder et al. 2012); network based
data Gindhaar& & Kumar 20066] Herzig et al., 2018); synchronizttion problems in robotics (Rosen
al. 2020); computer vision (Agrawal al. 2006): problems like multi object tracking where
many natural questions are invariant under the rearrangements of object labels (Kondor et al. 2007);
atomic physics (Seko et al., 2019); learning permutations (Huang et al., 2009h: Gaussian mixture models under group actions (Brunel] 2019). among many others (Bandeira et al. (0155). Significant
recent trends include neural networks that are equivariant under group actions on the data (Kondor &
Trivedi 2018 Worrall et al.
2016 Weiler et al. 2018a Thiede et al. 202 and related convolutional neural networks (CNNs) (Kondor et al. 2018 8 Cohen et al. 2018b Niepert et al. 2016: Defferrard
al. 2016 Cohen & Welling
et al.) 2018a Sal Esteves et al. 2018 Weiler et al./ 201 1b);; 2014 Perry et al. 2019; Bendory et al. 2017
multi-reference alignment (MRA) (Bandeira et al.
Sorzano et al. 2010 Abbe al. 2018 Fan al. 2020) and cryo electron microscopy (cryo EM)

---

Under review as a conference paper at ICLR 2022
under the action of the relevant Euclidean isometries (Singer et al. 2018 Hadani & Singer 2011 Bendory et al., 2020: Bandeira et al. 2015a); and so forth.
Invariant functionals. A significant class of observables (i.c., functionals of the data) that attract natural interest in this setting consist of those that are invariant with respect to the group action under consideration; e.g., mutual distances under the action of group of isometries, the relative order of two objects under the permutation of their labels. In this work, we focus on a fundamental category of such observables, called class functions, that are invariant under the conjugation action of group.
The conjugation action. Group action by conjugation is one of the foundational ways in which group act, and usually corresponds
change of basis, or relabelling of objects indices. A simple example is accorded by data in the form of matrices, where conjugation by an invertible matrix translates into a change of Euclidean basis, leading to the presentation of the information in a different co-ordinate system. In this setting, any function of the spectrum of the data matrix remains invariant under the change of basis (i.e., the conjugation action), and is clearly a significant feature to study. Yet another ready example is accorded by the permutation of the node labels in network, which leaves invariant important network properties, such as diameter, subgraph counts and other aspects of network geometry, as well as the spectral properties of the network.
Symmetries, group representations and Fourier analysis. Fourier analysis is a central tool in fundamental machine learning tasks, entailing vast collection of concepts including bandlimited functions and low pass filters, productively focussing on the low frequency part of the Fourier spectrum of a signal as the most significant component. At a conceptual level, much of this originates from the actions of the translational group of symmetries acting canonically on signals defined on Euclidean spaces; in particular, the structural simplicity is largely consequence of the fact that these groups are abelian or commutative.
However, natural learning scenarios where the canonical symmetries form a non-abelian group (i.e., non-commutatiive) are numerous; even on Euclidean spaces, the translational symmetries when augmented with rotations constitute ready example. In such settings, group representation theory (Simon 1996) accords an extension of many of the Fourier analytic concepts; for instance the expansion of function in terms of matrix-valued Fourier coefficients indexed by the so-called irreducible representations of the group. For a more detailed discussion on the fundamental synergies between Fourier analysis and group representations, we refer the reader to See. E in the appendix.
A non-linear conjugation invariant learning paradigm with neural networks. In the present work, we are focussed on learning conjugation invariant functions (i.e., class functions), which happen to accord a much simpler version of the non-commutative Fourier analysis discussed above. This is realised via an orthogonal linear basis of the so-called irreducible characters, which are essentially traces of certain minimal matrix representations of the group, and are well-understood in many concrete applications (c.f. Sec. E in appendix for details). It turns out that the space of irreducible characters exhibit much richer structure in the form an algebra, which entails that it is closed under polynomial combinations. As an upshot, using polynomials of a few irreducible characters of relatively low order, one is able express much more complicated characters of substantially higher order; leading to an approximation paradigm for general class functions via non-linear, polynomial combinations of a small alphabet of irreducible characters.
In implementing our programme, a fundamental role is played by neural networks, which allow us to effectively implement this non-linear approximation scheme. Our approach, in essence, leads to a global co-ordinate system for learning conjugation invariant functions on groups. Viewed from the perspective of function space approximation, our paradigm may be seen as kind of non-linear dimension reduction tool for class functions.
Groups acting on homogeneous spaces. In some applications, the group of symmetries G acts on a set X of objects (e.g., rotations acting on a sphere): such a set (under mild transitivity assumption) is referred to as a homogeneous space of the group. Our setup may be extended to cover such settings, using a canonical 'lift' of any function f X + R to function f : G + R that satisfies f = o r, for a standard quotient map π : G + X DDmmmit & Foote 2004). Stipulating that is ingiugation-ivvrrian is equivalent to f being [G. G -i-invariant on X, where [G, Gi is the so-called commutator subgroup of G (c.f. Lemma C. in appendix). This covers the setting of functions f that the permutation group S,, classification problems on the dihedral group Dan, and so on. For a detailed
constant the orbits of |G, Gj acting on X. Such functions include binary classifiers
2

---

Under review as a conference paper at ICLR 2022
discussion, refer the reader to Sec. C in the appendix. Further applications of paradigm to groups acting on homogeneous spaces can be obtained via a general averaging paradigm, e.g. in the context of image aligmment problems (c.f. Proposition 2.1).
Related literature. Class functions have appeared in various forms as useful methodological tools in the machine learning literature. These include the study of bi-invariant kernels in the context of RKHS on groups and homogeneous spaces (Jebara & Kondor 20088; applications to problems of multi-object tracking Kondor al. (207); y learning permutations (Jebara & Kondor 2008); diffusion kernels on graphs Kondor & Lafterty (2002); Saloff-Coste) (201), and so on. Yarotsky (202)) examines an invariant theory based approach learning under general symmetries via two layer neural nets with rather complex polynomial inputs; in contrast our approach inputs the ubiquitous group characters and approximates polynomials of high degree, via a few-layer network architecture that exploits the compositional aspect of neural nets in non-trivial way. To the best of our knowledge, our approach to efficient learning of conjugation invariant functions through the lens of group character theory appears to be rather novel, and prior literature in similar vein appears to be highly limited.
2 CONJUGATION INVARIANT FUNCTIONS AND THEIR APPLICATIONS
Our interest in this paper would be focussed on the so-called class functions, so we begin with a concrete definition.
Definition. Let G group. Two elements v, y E G are said to conjugate if 31 such that txt A function f G S for any set S is called a class function if [(aat- = (xx VI E G.
Conjugacy is an equivalence relation, partitioning G into equivalence classes which are referred to as conjugacy classes. It follows from the definition that conjugation-invarian functions are constant on these conjugacy classes, hence the name class functions.
Class functions on SO(3) and S,, Elements of the 3-D rotation group SO(3) are precisely 3 x orthogonal matrices with determinant equal to 1. Two elements of SO(3) are conjugate if and only they are similar matrices. This means that class functions on SO(3) only depend on the matrix spectrum of the elements of SO(3). In fact, every R E SO(3) is similar (via conjugation) to block
/cos cos
sin 0
()
diagonal matrix of the form
sin 0 0
0
In geometric terms, the conjugacy classes of
0
1/"
SO(3) are the sets of rotations by the same angle about different axes. The trace of these matrices is an example of a class function; tr( [?) = 1 + 2-22o cos
In the of the symmetric group Sn, permutations lie in the same conjugacy class if and only they have the same cycle shape. Since cycle shapes are conveniently labelled using partitions, the conjugacy classes of S, are most commonly labelled using partitions of n.
Class functions arise in many natural settings in machine learning. We provide below several such scenarios where class functions are of key importance.
general averaging paradigm. We first provide general setting where class functions arise naturally through process of averaging over the group: conjugation invariant functionals often emerge in practical problems through such procedure. Let G' be a group acting on a space X; that is for every g E G, we may associate map T, X + X such that T. idx the identity map on the space X (where is the identity element in the group G), and TyA = Tg Tj Vg, h E G. Let be the left Haar measure on the group G. i.e., du(g h) = dy(h) for all g. G. Then we may state:
Proposition 2.1. Let f: X x X + IR be such that [[g(x), g()) = f(x, v) Vx, y E X, E G. For any pair z, E X and T e G, define (T) == Sa ((')(())))))))))))))))))())) ((())(()))(())dd( d(()), Then fz, is a class function.
Functions of as in Proposition 2.1 that are invariant under the diagonal action of G naturally occur in wide array of settings; prominent among them being in the form of distances (or angles) Euclidean space X under the action a group of isometries G. For a concrete use-case, we refer to the image alignment application below.
3

---

Under review as a conference paper at ICLR 2022
Proof of Proposition 2.7
Given any h G, we have
1(1Th-'' "())) = -sa S(Th (r)), h- ( (())))
(
= (T)
The third equality is due to left-invariance of j and setting g' = h h-
Image Alignment. Image alignment problems have received considerable attention in recent years, and furnish natural example of class functions. To set the stage, we consider spherical images, which are well-motivated by projections of planar images onto the northern sphere (Kondor et al. 2018. Jebara& Kondor 2008). images in the form of photos taken using a 360" camera. and so on. In the setting of Proposition 2.1 we set G = SO(3), X = S² and f(r,y) y) to be the Euclidean distance between and y, which would naturally be rotation invariant. Then fz.,, (T) is measure of how well an image centered at x aligned with an image centered at y after applying the rotation operator T. The quantity Ma. = miny (T) captures the maximal alignment between the images, and can be used c.g. for classification tasks (e.g., if is prototype and y is image, then classify to the category of if Mazy smaller than a threshold). Proposition 2.1 demonstrates that fz.g is class function on 5O(3).
Quadratic Assignment Problem. Let P, denote the group of n x n permutation matrices; that is matrices having exactly one entry equal to 1 in each row column, and the remaining entries being 0. The quadratic assignment problem (QAP) is fundamental problem in combinatorial optimization Koopmans & Beckmann (1557), where the goal is to find arg min tr tr(ABX")): we will consider
XEP,
this problem in the settung where A E Pn and B is a general n x n matrix.
Proposition 2.2. Let f : Pn + IR be given by ((A) == min XeP,
tr(AXBX²), and B be an
matrix. Then f is a class function.
Proof. We verify that f is class function. Fix any Q, A Pa. Note that Q = QQ1 S(QAQ-1) min xeP,
tTQQQf XBX*)= min xeP.
min tr(A" XBX XeR
min t<((Q""))(("") x)) XeP.
= [(A).
This gives us a stopping algorithm (or target) for QAP in the following sense. Once we learn the function f. we could obtain or approximate the objective minimum f(A) for the QAP. We can then use some optimization algorithm (such as gradient descent) to update the matrix X in order to decrease the objective tr( AX Bx*). ), and terminate the optimization process once tr tr(AXB"") - ((A) <6 for some acceptable eтror tolerance threshold c > 0.
Testing on comparative rankings. Denote (1.2.... nn by [n]]. Let S,, be the symmetric group on [n]. Suppose that we have two real-valued functions fi, f2 [m] + R. Then, fi and f2 would induce orderings a and 02 respectively of [n]. For instance, we could have n individuals and fi (k), (2() resp. the height and weight of individual k, leading (denoted resp. by 01. 02). A natural question is the comparative analysis testing whether they approximately similar. In such considerations, of natural interest are statistics like the number of individuals having the same rank, given by L. = n EkE(n) 1 [(1(()==2(()) =
their ranking by heights weights
such rankings, e.g.
n EkEIn 1 107 105' [k()==)])> where is the indicator function.
Let f Sn R be the function f(a) = Ekejm [(((k)=)) for all E Sni notice that Ln = f(z 01). For any n, a E Sn, we may compute f(tOT=)) = n Eke(n) | 1 = Exeen]] 1 1[x=-1())==-10) f(r). This demonstrates that the important statistic C, is class function.
4

---

Under review as a conference paper at ICLR 2022
Multi-object tracking. In the multi-object tracking problem, there k objects with labels {I....,k), and we observe their arrangement which evolves with time; e.g. the evolution of the formation of jets flying in air show. The data is succinctly described in terms of permutation (1) mapping each label to its position in the arrangement at time t. Most of the fundamental questions about this model are actually independent of the labels; e.g., whether the starting and the final arrangements are the same, or the first time t to at which (tt) undergoes a change. etc. Any change in object labels amounts to a conjugation a (t) + (t((t) for some permutation π, leading to the fact that the answer to the above natural questions pertaining to relative order are all class functions.
TENSOR PRODUCTS AND THE ALGEBRA OF CHARACTERS
The theoretical foundations of our approach are underlaid by the theory of tensor products of group representations, which manifests itself in the form of polynomial algebra structure on group characters. Below, we provide a rudimentary outline this theory, focussing on aspects that are fundamental to our approach. For account of group representation theory essential for our approach, we refer the reader to Sec. E in the appendix.
The character Xp of matrix representation P of group G is the function X G + C defined by x(=)) = tr(p(z)). The characters inherit the inner product from the T.2 structure the group G. We call d, the order of or Xp- If is an irreducible representation, we say that X₂ is an irreducible character. Since tr(T-1A) AT" tr(.A), it is evident that X, is a class function. By the celebrated Peter-Wey: theorem (Simon 1996). the set of irreducible characters form an orthonornal basis for the space of square integrable class functions.
Let P1 and P2 be two representations of G with corresponding characters X1 and X2 respectively. The tensor product representation is defined as P1 @ p2( (g) @ P2(9) for all E G (to be understood in the form of tensor products of matrices). In general, if #1 P2 is representation of G' even if P1 and A are irreducible. However, the theorem of complete reducibiliity (Simon 1996) tells us that must decompose uniquely direct sum of irreducible representations Gf
irreducible
(1(g) & p2(g)=
BC P2.P.
(1)
PER(G)
and R(G) is the set of all irreducible representations of G; we also note the simple relation X 0p2 X + Xxp- Let X1s2 be the character corresponding
where p just means the direct sum of m copies of p. ① m
Pi & p2. An important observation is that Xiw2(g) = xi (0)x22)) relation that may be understood in the context of the tracial identity for matrix tensor products; namely, tr(A & B) (r)) Thus, we have
(1())2(0)) Σ (pppa.pXoo))
( induces a canonical polynomial algebra structure on characters, which we will exploit in our approach. In the literature, the coefficients Cpr.Pa.p are known as the Clebsch- Gordan coefficients; they are well understood for many groups (Costa & Fogli 2012). These coefficients are known to be of fundamental importance in quantum mechanics, where they arise in the consideration of independent quantum systems.
4 OUR PARADIGM: NON-LINEAR APPROXIMATION VIA NEURAL NETWORKS
4.1 LINEAR VS NON-LINEAR APPROXIMATION
In this work, we focus on the task of effective approximation of class functions with a limited alphabet (i.e.. dictionary or collection) of irreducible characters, thereby achieving a kind of non- linear dimension reduction. Peter- Weyl theory guarantees that the set X() of irreducible characters form an orthonormal basis for the space of class functions G. Therefore, in principle, any class function f can be learned simply by linear regression onto (G). However, X(G) is finite if and only if G is finite; so for infinite compact groups (such SO(3)) even large finite groups,
5

---

Under review as a conference paper at ICLR 2022
only aspire to learn f from irreducible characters upto sufficiently high order while maintaining a reasonable computational expense. In natural applications, the class function of interest may be highly irregular (e.g. finite linear combination of indicators in classification problem); since characters are generally highly regular (e.g., smooth) functions, we would require a very large numher of characters to obtain effective linear approximation of irregular functions.
4.2 NON-LINEARITY VIA NEURAL NETS
The cornerstone of our approach is to exploit the non-linear, polynomial tensor algebra structure of the group characters in order to amplify and augment the expressive power of small alphabet of irreducible characters (c.f., Section 3). In implementing our programme, a key role is played by neural networks, which allow us to obtain effective non-linear approximations of class functions in an efficient manner. Apart from their well-known effectiveness in tackling non- non-linearities, we do not need to a-prrori specify explicit polynomial expressions of higher order characters in terms of those in the alphabet; such expressions can be complicated to compute explicitly.
4.3
A NEURAL NETWORK BASED CONJUGATION INVARIANT LEARNING PROTOCOL WITH A SMALL ALPHABET
We delineate below the main steps of our procedure to approximate class function f on a group G.
Input. A small subset of irreducible characters X2,,X,..... Xw) CRG) as alphabet; input data in the form of pairs {9t, ((:) 9i E G; I i S m].
Step 1. For each $ E m, compute V, = (x. (2.9)).... Xu (g:)).
Step 2. Use {(v., ((:) < S m} the training dataset to train neural network with width for the initial layer, and width for the final layer.
Step 3. For any new input argument E G, we compute the prediction f(g) as follows:
Step 3a. Compute V, (x1 (g), X2)), ..... X (g)).
Step 3b. Perform forward propagation in the neural network output in Step 2 above, with input yg.
Step 3c. Output the result of Step 3b above the estimate (g))
4.4 A GLOBAL COORDINATE SYSTEM AND NON-LINEAR DIMENSION REDUCTION
Our approach, in essence leads to a global co-ordinate system for learning conjugation invariant functions on groups (see Sec. in appendix for detailed discussion). The global co-ordinates of a point y E G would be given by (x1 (g),,..., X (g)), where {x,) is our small alphabet of characters. This stands contrast to local co-ordinate systems on manifolds or Lie group, which are based on local charts and therefore even such local charts are not available. Further, our alphabet can effectively approximate general class functions via non-linear combinations, thereby according us low dimensional non-linear co-ordinate system to approximate the infinite dimensional space class functions. From this perspective, our limited alphabet of characters may be seen as a non-linear dimension reduction tool for class functions.
effective only in small neighbourhoods; for discrete groups,
THE EXPRESSIVE POWER OF SMALL ALPHABETS AND NON-LINEARITY
In this section, we explore the expressive power small alphabets characters for some significant groups. We demonstrate that non-linear, polynomial functions of a very small collection of irreducible characters in groups such as SO(3) and SU(3) are sufficient to generate all characters in these groups, thereby leading to an approximation of arbitrary class functions. This provides a strong theoretical basis to substantiate our approach of learning arbitrary class functions using deep neural networks with a small set of low order irreducible characters global coordinates. Although the results presented in this section focus on SO(3) and SU(3), we believe that similar analysis can be extended to other groups of practical significance. Such groups often admit detailed representation theory in general, and an explicit Clebsch- Gordan tensorial decomposition in particular, stemming from their importance in physics and applied mathematics. We refer the reader to Sec. A in the appendix for

---

Under review as a conference paper at ICLR 2022
discussion the symmetric group Sn. For computational techniques for general groups, see Unger (2006); Babai & Rónyai (1990) in the discrete and Blaha ) Green (1971 in the continuum setting. The degree of the polynomial in small alphabet that needed to express higher order character may be taken as a measure of the expressive power of the alphabet, with a low degree signifying high expressive power. Below, we demonstrate that for groups of fundamental interest in applications, we are able to obtain high expressive power with a very small alphabet of irreducible characters.
5.1 EXPRESSIVE POWER AND CLEBSCH- GORDAN STRUCTURE FOR SO(3).
The irreducible representations of SO(3), the 3D rotation group, may be conveniently labelled by {Pz j E ]. where each Pj is of order 2j + (po is the one-dimensional trivial representation). Let Xj be the corresponding irreducible character. The Mebsch--Gorda decomposition for SO(3) turns out to be very explicit. For 2 m, we have
Pi & Pm Pi+m @ P1+m-1 B ..... pt-m-
In terms of characters, we have for 2 m
Xt Xm XI-m + Xi+m-1 +... Xt-m-
(3)
Theorem 5.1. Fix any 1 2 0. Then, XI E Z[xi]. Moreover xi is polynomial of degree I.
Proof. Setting m = 1 in 3 yields
X++1 XI
XI-1, 121 1.
(4)
We will prove this result by induction on
Base case / < 1 Xu is the trivial character, which is the constant function Xo Vg SO(3), so is a polynomial of degree O. We of course have that X1 is a polynomial of degree in -|xi]-
Suppose that for every 0 < j S I, Xy lies in Zixil and that it is polynomial of degree j. We want to prove that X1+1 lies in [ and that it is a polynomial of degree + 1.
By 4. have X Xi X1 Xi XI-1. 1. By our inductive hypothesis, the right-hand side is evidently a polynomial of degree 1 + 1 in 2(x1].
5.2 EXPRESSIVE POWER AND CLEBSCHIGGRDDA STRUCTURE FOR SU(3).
SU(3), the group of 3 x unitary matrices with determinant 1, is of key interest in the celebrated Yang-Mills theory and related areas of physics, and has seen recent surge of activity from machine learning perspective (Matsumoto et al. 2021 Anderson et al. 2020). The irreducible representations of SU(3) may be succinetly labelled as [D),, q) P,g E 220 f in physical terms, p is the number of
quarks and q is the number of antiquarks (D(0, 0) is the trivial representation) (Hall 2015). D(p, q) known to have order } (p + () (p + q + 2). There
many algorithms for computing the Clebsch-Gorde Gordan coefficients for SU(3) general; however, they are rather complicated in nature. We list three simple recursive relations which sufficient for our study of expressive power
D(p,0) & g) = D(p.g) 4) @ DD( 1,0) @ D(O, 1)],
p.q > 0.
D(p, 0) & (11, 0) = D(p + 1,0) @ D(p 1,1), p> 0. D(0.g) @ D(O, 1) = D(0. +1) @ D(1,q -1), <>0. 0. In terms of irreducible characters, we have respectively for p.q > 0:p > and > 0:
P = 0. - u.4-1, x+100 10 x = 0x 2.9 1
10
(5)
We now use these recursive relations to prove by induction on + y that every irreducible character x P.9 occurs polynomial of the two lowest order (order 3) non-trivial irreducible characters x 1.0 and n.1
Theorem 5.2. Fix any p. q E Ezo. Then, x E - Moreover, P is polynomial of degree at most p q.
7

---

Under review as a conference paper at ICLR 2022
Proof. We prove the statement by induction .N - q-
Base case N = p S 1: x0.0 = 1,, E Z 1.0 .x.'). There is nothing to show here.
Suppose that xr.* E 2 21x110, x I. having degree I + s, whenever + S N. We want to prove that x E _ x²" x with degree <ptg g, whenever p + - + 1.
Case 1: p m g N + +1p,, 0. By 5 we have x = x 0.9 x-- 1,0x 0. The right-hand
side is a polynomial of the form x" such that r + 8 N, therefore x E Z 1.0 x as required.
Case 2: N +1.9 9 O. By (5) we have X x x x x N
1,1, Once again, the right-hand
side a polynomial of the form x such that r + s S N, therefore X N+1.0 E _ xx.
Case 3: p 0,g q N + By 5),
we have x =_
x 1
x Once again, the ,,N
right-hand side is a polynomial of x such that r + E N, therefore x
E Z x x O
6 EXPERIMENTS
In this section, we provide brief description of demonstrative numerical experiments to show the feasibility and efficacy of our learning paradigm in several distinct contexts, The reader may refer to the appendix Sec. F for a more detailed description and additional experiments. We used TensorFlow (Apache License 2.0) and Keras (MIT License) to run our experiments Abadi al. (2015): Chollet itt al. (015) on an Intel i7-5500U chip.
The group SO(3) the standard rotation group on the Euclidean space RR significant in many applications such as imaging. Let Xy be the irreducible character of SO(3) as mentioned in Sec. We use fully connected neural network with 3 hidden layers (ConjInv) with the ReLU activation function at every layer except the last and input alphabet {xo. (i........ X10} (see Sec. to learn class functions f (specified below) on SO(3). For each experiment, 24000 points g B,) E [0, 2T] x [0, π] x [0, 2T] SO(3) are picked uniformly at random to generate our data of the form (g. f(3) (note that class functions on SO(3) only depend on (). We split our data into train, validation and test sets with 20000, 2000 and 2000 points respectively. Throughout this section, we minimize the squared error loss (MSE) using Adam Kingma & Ba (017). Hyperparameters are tuned according to the validation set and the final performance is measured the test set.
5.1
We benchmark our results against a fully connected neural network with 6 hidden layers (DeepEuler) that takes the group elements g (a, () E SO(3) directly inputs well linear regression model (Regression) with input alphabet (Xo= X1, X32) The Fuler angles fully describe the group elements in SO(3), and thus comparison of DeepFuler with ConjInv provides concrete measure of the effectiveness of an alphabet of irreducible characters. On the other hand, since characters form functions, regression on characters will provide
linear basis of the space of conjugation-invaric nearly exact learning if the number of characters is high, which suggests such regression as another benchmark to compare against. Our experiments demonstrate that conjugation invariant learning with group characters outperforms both DeepEuler and Regression.
Learning continuous class functions on SO(3). We randomly generate 100 class functions as Gaussian linear combinations of X30, X.1...., X to be learned by ConjInv, DeepEuler and Regression as described above. The three models are compared based on their log-loss on the test set. See Fig.
Learning discontinuous class functions on SO(3). We randomly generate 100 discontinuous class functions f by taking Gaussian linear combinations of some binary valued indicator func-
0. < 3 < 0.1mk 0.12m, These functions otherwise.
tions 1g, 11..... ..... . 1g, where 3,,,,,,7)
learned by ConjInv, DeepEuler and Regression described above. The three models compared based on their log-loss on the test set. See Fig. 2
Learning class functions S,. This is important model of a highly non-commutative discrete group that arises in various applications. For the detailed experiment, we refer the reader to Section F.1 the appendix.
Learning discontinuous class functions on SU(3). This is a crucial model of a Lie group that has significant physical applications, including in particular in quantum chromodynamies Halzen &
8

---

6 Under review as a conference paper at ICLR 2022
DeepEuler vs Conjinv (continuous)
Regression vs Conjinv (continuous)
12
mean 2.70486
15.0
mean 4.303261
10
12.5
Frequency
Frequency
10.0
7.5
5.0
2.5
0.0
3 4
1
3
log( MSE((eepEuler) [SE[(on)lnn)]
logí MSE(Regression) MME((Conjnvv)
Figure
DeepEuler vs Conjinv (discontinuous)
Regression vs Conjinv (discontinuous)
15.0
moan 6820083
15.0
mean 2 222662
12.5
Frequency
10.0
Frequency
10.0
7.5
5.0
5.0
2.5
2.5
1.5
2.5
4.0
4.5
1.50 1.75 2.00 225 2.50 2.75 3.00 1.25
logl MSE(DeepEuler) MSE(ConjInv))
logl MSE(Regression) MSE(ConjInv)) ]
Figure 2
Martin (0088; additional computational challenges result from the matrix entries being complex numbers. We refer the reader to the Section F.4 in the appendix.
DISCUSSION
We investigate conjugation invariant functions groups, and propose effective learning paradigm for such functions via non-linear functions of a small alphabet of characters. We substantiate our approach via theoretical analysis several groups significant in applications, and via synthetic experiments using neural networks to efficiently capture the non-linearities.
To knowledge, the present submission is the first work to explore the problem of learning conjugation invariant functions. Another key aspect of our work is to propose the extensive use of group characters, particularly their non-linear polynomial functionals, under group action. Further, we set up our approach to be applicable in the context of the actions of any group, whereas many of the popular methods (such CNNs) are tailored specific kinds of group actions, or specific application domains. As such, there is very little benchmark to compare against for the problem at hand. We emphasize that, given that this is the first exploration in this area, our experiments are more for demonstrative purposes to provide proof-of-concept for our paradigm; the main contributions the paper being the realm of theory and ideas.
tool in machine learning
The investigations in the present paper call forth natural directions for future work, including experiments with real-life data, a theoretical as well as experimental study how to optimally choose the size of the input character alphabet in relation to the computational budget available (e.g.. depth of the neural net), a theoretical analysis of expressive power that subsumes general classes of group applications such graph neural networks Maron et al. (2018): Azizian
actions, and & Lelarge (2020); Keriven & Peyrě (2019). We believe that our work will motivate new perspectives within the general ambit of learning under group actions.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: scage machine learning heterogeneous systems, 2015. URL https: //wwwwww.... tensortesort low, org/ Software available from tensorflow.org.
Emmanuel Abbe, Tamir Bendory, William Leeh, João Pereira, Nir Sharon, and Amit Singer. Multireference alignment easier with an aperiodic translation distribution. IEEE Transactions on Information Theory, 65(6):3565-3584, 2018.
Amit Agrawal, Ramesh Raskar, and Rama Chellappa. What is the range of surface reconstructions from gradient field? In European conference on computer vision, pp. 578-591. Springer, 2006.
Lara Anderson, Mathis Gerdes, James Gray, Sven Krippendorf, Nikhil Raghuram, and Fabian Ruehle. Moduli-dependent calabi-yau and su (3)-structure metrics from machine learning. arXiv preprint arXiv:2012.006655 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006. 1 15646, 2020.
László Babai and Lajos Rónyai. Computing irreducible representations of finite groups. Mathematics of computation, 55 55(192):705-722, 1990.
Afonso S Bandeira, Moses Charikar, Amit Singer, and Andy Zhu. Multireference alignment using semidefinite programming. In Proceedings of the 5th conference on Innovations in theoretical computer science, pp. 459 470, 2014.
Afonso S Bandeira, Yutong Chen, and Amit Singer. Non-unique games over compact groups and orientation estimation in cryo-em. arXiv preprint arXiv: 1505.000000 2015a.
Afonso Bandeira et al. Convex relaxations for certain inverse problems on graphs. 2015b.
Tamir Bendory, Nicolas Boumal, Chao Ma, Zhizhen Zhao, and Amit Singer. Bispectrum inversion with application to multireference alignment. IEEE Transactions on signal processing, 66(4): 1037-1050, 2017.
Tamir Bendory, Alberto Bartesaghi, and Amit Singer. Single-particle cryo-electron microscopy: Math- ematical theory, computational challenges, and opportunities. IEEE signal processing magazine, 37(2):58-76, 2020.
Stephen Blaha. Character analysis of (n) and su (n). Journal of Mathematical Physics, 10(12): 2156-2168, 1969.
Vitto-EEmaanué Brunel. Learning rates for gaussian mixtures under group action. Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume of Proceedings of Machine Learning Research, pp. 471 491, Phoenix, USA, 28-28 Jun 2019. PMLR. URL ht http::/pooceainggg.... http:://poceciiinn.....gssss//sr html
François Chollet et al. Keras. https: 2015.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International Internationallooffeeeec conference machine learning, pp. 2990-2999. PMI.R, 2016.
Taco Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant cnns on homogeneous spaces. arXiv preprint 1 111811/00017 2018a.
10

---

Under review as a conference paper at ICLR 2022
Taco S. Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical CNNs. In International Conference on Learning Representations, 2018b.
norum
id=Hkbbd5x2Rb
Giovanni Costa and Gianluigi Fogli. Symmetries and group theory in particle physics: An introduction to space-lime and internal symmetries, volume 823. Springer Science & Business Media, 2012.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv preprint arXiv: 09376, 2016.
David Steven Dummit and Richard M Foote. Abstract algebra, volume 3. Wiley Hoboken, 2004.
Carlos Esteves, Christine Blancheeee Ameesh Makadia, and Kostas Daniilidis. Learning (3) equivariant representations with spherical cnns. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 52 68, 2018.
Zhou Fan, Yi Sun, Tianhao Wang, and Yihong Wu. Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model. arXiv preprint arXiv:2004.0000 2020.
Arvind Giridhar and Praveen R Kumar. Distributed clock synchronization over wireless networks: Algorithms and analysis. Proceedings of the 45th IEEE Conference on Decision and Control, pp. 4920.. IEEE, 2006.
HS Green. Characteristic identities for generators of (n), (n) and (n). Journal of Mathematical Physics, 1211022100-2113, 1971.
Ronny Hadani and Amit Singer. Representation theoretic patterns in three dimensional cryo-electron microscopy i: The intrinsic reconstitution algorithm. Annals of mathematics, 174(2): 2011.
Brian Hall. Lie groups, Lie algebras, and representations: an elementary introduction, volume 222. Springer, 2015.
Francis Halzen and Alan Martin. Quark & Leptons: An Introductory Course In Modern Particle Physies. John Wiley & Sons, 2008
Roci Herzig, Moshiko Raboh, Gal Chechik, Jonathan Berant, and Amir Globerson. Mapping images to scene graphs with permutation-innaaiian structured prediction. arXiv preprint arXiv: arXiv:/802.05455) 2018.
Jonathan Huang, Carlos Guestrin, and Leonidas Guibas. Fourier theoretic probabilistic inference over permutations. Journal of Machine Learning Research, 10(37):997-1070, 2009. URL
html
Jebara and I. Kondor. Group theoretical methods in machine learning. 2008.
Ramakrishna Kakarala. The bispectrum as a source of phase-sensitive invariants for fourier descrip-
tors: a group-theoretic approach. Journal of Mathematical Imaging and Vision, 44(3):341-353, 2012.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32:7092-7101, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Risi Kondor. A novel set of rotationally and translationally invariant features for images based on the non-commutative bispectrum. arXiv preprint cs/0701 /27, 2007.
Risi Kondor and Shubhendu Trivedi. On the generalization equivariance and convolution neural networks to the action of compact groups. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. 2747-2755. PMLR, 10-15 Jul 2018. URL http::/ppoccediin. mlr. www.:pressseee pitrss/v800 wttpss/vo//kkooo
htmml
Risi Kondor, Andrew Howard, and Tony Jebara. Multi-object tracking with representations of the symmetric group. In Artificial Intelligence and Statistics, pp. 211-218. PMLR, 2007.

---

Under review as a conference paper at ICLR 2022
Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-gorfe nets: fully fourier space spher- ical convolutional neural network. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchie and R. Garnett (eds.), Advances in Neural Information Processing Systems. volume 31. Curran Associates, Inc., 2018. URL ht: htwp//httpps/prrrcceedeggg neur ps. cc/ pdf
Risi Imre Kondor and John Lafferty. Diffusion kerness on graphs and other discrete structures. In Proceedings of the 19th international conference machine learning, volume 2002, pp. 315-322, 2002.
Tjalling C Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pp. 53-76, 1957.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint
2018.
Takuya Matsumoto, Masakiyo Kitazawa, and Yasuhiro Kohno. Classifying topological charge in su (3) yang-mills theory with machine learning. Progress of Theoretical and Experimental Physics, 2021(2)023D01, 2021.
Tobias Moroder, Philipp Hyllus, Géza Tóth, Christian Schwemmer, Alexander Niggebaum, Stefanic Gaile, Otfried Gühne, and Harald Weinfurter. Permutationally invariant state reconstruction. New Journal of Physics, 141100:00500,, 2012.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference machine learning, pp. 2014-2023. PMLR, 2016.
Amelia Perry, Jonathan Weed, Afonso Bandeira, Philippe Rigollet, and Amit Singer. The sample complexity of multireference alignment. SIAM Journal on Mathematics of Data Science, 1(3): 497-517 2019.
David M Rosen, Luca Carlone, Afonso S Bandeira, and John Leonard. A certifiably correct algorithm for synchronization over the special euclidean group. In Algorithmic Foundations of Robotics XII, pp. 64-79. Springer, 2020.
Laurent Saloff-Coste. Probability on groups: random walks and invariant diffusions. Notices of the AMS, 48(9):968-977) 97788899777700 2001.
Atsuto Seko, Atsushi Togo, and Isao Tanaka. Group-theoretical high-order rotational invariants for structural representations: Application to linearized machine learning interatomic potential. Phys. Rev. B, 99:214108, Jun 2019. doi: 1003/PhysRevB..tmm 99. 294214 URL hhtp:h:tt//iiiitt aps
prq/doi/Di 10. 1wwp//1y11//eeeeee 99. 29..1411... 214108
Barry Simon. Representations of finite and compuct groups. Number 10. American Mathematical Soc., 1996.
Amit Singer et al. Mathematics for cryo-electron microscopy. arXiv preprint arXiv:1803.00 100:10683.6444 2018.
Carlos Oscar S Sorzano, JR Bilbao-Castro, Shkolnisky, M Alcorlo, Melero, Caffarena- Fernández, M Li, G Xu, R Marabini, and JM Carazo. A clustering approach to multireference alignment single-particke projections in electron microscopy. Journal of structural biology. 171 (2):197-206, 2010.
Erik Henning Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets. arXiv preprint arXiv:2103.017/1 2021.
William Unger. Computing the character table a finite group. Journal of Symbolic Computation, 8148):847-862, 2006.
DW Vasco. Invariance, groups, and non-uniqueness: the discrete case. International, 168(2)473-490. 2007.
Geophysical Journal
12

---

Under review as a conference paper at ICLR 2022
M. Weiler, F. A. Hamprecht, and M. Storath. Learning steerable filters for rotation equivariant cnns.
In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 849-858, Los Alamitos, CA, USA, jun 2018a. IEEE Computer Society. doi: 10.1 htl.hhtps:////
reeecomnuterssscict...... org/10 1 1 CVPR. 201 & 00095
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data, 2018b.
Alexander Spence Wein. Statistical estimation in the presence of group actions. PhD thesis, Massachusetts Institute of Technology, 2018.
Daniel Worrall, Stephan Garbin, Daniyar Turmukhambetov, and Jourdan Gabriel. Harmonic networks: Deep translation and rotation equivariance. 12 2016.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, pp. 1-68, 2021.
13

---

Under review as a conference paper at ICLR 2022
APPENDIX TO CONJUGATION INVARIANT LEARNING WITH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
A EXPRESSIVE POWER AND CLEBSCH-GORDAN STRUCTURE FOR SYMMETRIC GROUPS.
Let Sn the symmetric group on n letters. Two permutations in S, are conjugate if and only if they have the same cycle shape.
Definition. We say that an m-tuple (A1, A.,..., Am) is partition of n if X E E A+11 S A and
n. The number of parts of is denoted by ((A) m.
We denote the set of all partitions of by P(n). A natural ordering of P(n) the lexicographic order.
Definition.
A and p are partitions of n, we write a and only if the least j for which A F Pj satisfies X, > Mi.
Cycle shapes may be canonically represented by partitions of n. well known fact that for any finite group G, the set of irreducible representations of G over C is in bijection with the conjugacy classes of G (in particular, character tables for finite groups are square). Therefore, it not surprising that the irreducible representations of S,, may be conveniently labelled by the partitions of n. For each À E (n)). there an associated irreducible representation V (known as Specht modules in the literature) of Sn. Some examples are the one-dimensional trivial representation ((a) and the miedimnesioonll sign representation y(1"), where (1") is shorthand for the partition (1, 11. 1) E (n)). For more detailed description of the Specht modules, the reader may refer to Gordan James's classical textbook James (2006).
Definition. Let A E P(n). The Young diagram of À is defined to be the set
[>] ((a,b) 2oo Zoo 1 s
Aa).
The elements of [X] are called the nodes of
Definition. The conjugate partition À is the partition X' (M, X2....) such that X; # 2
1 X i).
In other words, the Young diagram [X] may be obtained by swapping the rows and columns of [A]:
[^] = ((b,a) Z>o x Z (a. [사]]
In particular, note that (X' X. This induces pairing of partitions in P(n).
The Young diagram a partition À may be represented pictorially by a diagram. For each (i,j) e [A],
insert box into the 7h row and jth column of the diagram.

---

Under review as a conference paper at ICLR 2022
Example. Suppose that À = (7,6,5,5,1) P(24) so that (())((()))))))))())) = 5. [A]
- = (5,44,2,, 2,,1), [
The Clebsch-Gordan coefficients for S,, are also known as the Kronecker coefficients in the literature. fundamental problem the representation theory of Sy to understand the Kronecker coefficients. Apart from special cases Bowman et al. 20155; 5) Tewari (2015); Hamermeshi (2012) such as when the partitions have only two parts or are shaped, there are more questions than answers in general.
fundamental yet simple method of constructing representations of S, is by taking an existing representation and tensoring with the one-dimensional sign representation V(1"), Doing this for the irreducible Specht module V produces its conjugate Specht module Vx
& ((1) yx
E
Let X be the irreducible character corresponding to V terms of characters, the above result is simply
xx
(1)
Let RG) denote the of irreducible characters of group G. This means that we may pick single
representative character X for every pair of characters (x* x²) when curating an alphabet to generate RSS,) ) as polynomial in X]. In other words, the size of the minimal generating alphabet X is at most about half that of R(S.). We believe that in most cases, the minimal generating alphabet size will be even smaller. However, due to the difficulty of working with Kronecker coefficients, general result of this form is beyond the scope of this paper and may be discussed a future work. We demonstrate this with small example using only one more basic fact Hamermeshi (2012) about Kronecker coefficients. For any n E Zoo and X E P(n).
x (n-1111) (# 1)X Σx
where the sum is over all partitions y whose Young diagram [n] obtained from the Young diagram one less than the number of Example. Let n 6. We list all 11 partitions of 6 in the following table:
[A] by removing node and adding another node, and # different row lengths of [A].
A
6
15
(4
14,
(3,3)
(3, 2, 1)
(2, 1,1,
1311,111)
(2,2
(3, 2,
Recall that (6) is the trivial character that takes constant value 1. By (1) we have R[R(Se)] (5,1), x (1.2), x (1.1.1), x (3.3), (3.2.1), ,,2,,,,xx (1))). We show that in fact,
R [ A := (5.1) x (1.2)
(1
x (4,1,1) x (3.3) and X (3.2,1) A. By we have X (5.1) (5,1) x5,1) suffices to show that x (1.2) + (1.1,1) thus x (11.1) A.
(5.1)
2

---

Under review as a conference paper at ICLR 2022
Using 2 again, we obtain
(4.2) = ((.1) 1) + x44.2) + x (41111) x((0,)) + (3.2.1) and
(
x (4.1,1) ( (42) + +x (411111 + (82.1) + x (3.111.1)
Hence, (3.3) + xx (0.211) A and (32.1) ((.11.1)) E A. Since (3, 1, (4, 1y, have
(3.1..111 x (4.111) X (1)
by
Therefore, x (3.211) and X (3.3) A.
This completes the proof that [S.) R[x (5.1), (1.2,, x(
Remark. Similarly, one show using (1) and (2) that R (R(())] = R[ x(5.2) (00)),x0))) Note
that [P(7)] 15.
B GLOBAL COORDINATES VIA IRREDUCIBLE CHARACTERS
In the main text, Sec. 4.4, we indicated that our approach, in essence leads to a global co-ordinate system for learning conjugation invariant functions groups. To be precise, the global co-ordinates of a point 9 E would be given by ( Xa (=) (g)), where {xi) is our small alphabet of characters. Herein,
needed to abbreviate in the main text. We emphasize that, these global co-ordinates are with a view to learning conjugation invariant functions on the group G. We recall here that conjugation invariant functions are constant on the conjugacy classes, which are the orbits of the conjugation action of G' on itself. For optimality of representation, is natural that coordinate system for efficient learning of class functions would be constant on the conjugacy classes of the group. This is satisfied by our character- induced coordinate system (x1 (+),... : (-). which constant on the conjugacy classes G. Thus, in precise terms, these global coordinates parametrize the space of conjugacy classes of the group, which is minimally sufficient for describing class functions on G. On Lie group (such as SO(n) or SU(n)), the conjugation action of the group is smooth action, i.c. the map 7 7(g, z) gag smooth map taking G x G + G. The decomposition of the group into conjugacy classes manifold, c.f. (Lawson Jr 1974 Walschap 2012 into
discuss further details and geometrie implications of this, which
corresponds to a foliation of G (viewed submanifolds (called the leaves of the foliation) corresponding to the conjugacy classes, on which any class functions constant. Thus, from geometric point of view, the coordinates induced by the irreducible characters provide a global parametrization for the leaves of the foliation of G into its conjugacy classes.
C LIFTING FUNCTIONS ON HOMOGENEOUS SPACES TO GROUPS
In this section, we elaborate the ideas articulated in the main text, pertaining the lifting of functions from homogeneous spaces to groups, thereby substantiating our focus on studying functions defined on groups.
In our considerations, we mostly focus on the scenario where the conjugation invariant function defined on the group, and the group is envisaged to be acting on itself. In many situations of interest in ML, the group of symmetries actually happen to act on a set of objects that are directly not elements the group itself. Such a set on which the group acts sometimes referred to as a homogeneous space of the group. However, we demonstrate that our setup is easily extended to cover such situations.
In the common situation where the group G acts transitively the homogeneous space X (i.e. any pair elements in X can be mapped to each other by appropriate group elements, e.g. the Euclidean rotation group acting the sphere), it is known that the homogeneous space X can be identified with a quotient of the group G by a certain subgroup (the stabilizer subgroup of any given point in X). This is entailed by the celebrated as the coset space of such a stabilizing subgroup of G.
Theorem. In fact, this essentially identifies X
In the context of work, the upshot of this is that, any function f : X + R be 'lifted' to function on G, which is to say that there is function f G +> I and surjective quotient map G + RR such that (g) [(*(g))Vg G. Since is surjective, the functional value of f at
3

---

Under review as a conference paper at ICLR 2022
any point E X can be obtained from f in accordance with the above formula. This procedure
is completely canonical, and can be easily carried out explicitly in a general setting. The lifting
G
construction is succinetly summarized in the following commutative diagram:
-
f
R
simple yet informative example of the above scenario is accorded by the action of the permutation group S, on the labels [yx] of a set X of n objects. If we fix a specific object, then its label is stabilized or left unchanged under this action by Stab subgroup of S,, that permutes only the labels of the remaining n - 1 objects, and is thus isomorphic to Sn The set X, by the preceding discussion, is therefore in bijective correspondence with the coset space / /Sta;; notice that since Stab = S, we have |S,//ttab = |s,/ -n n. The cosets of the subgroup Stab form a disjoint partition of Sp: in other words, S, UStab,, where Stab; are the disjoint cosets of Stab inside S,, Any function f X + R can be lifted to a function according to the above recipe as follows. Any E Sn belongs to unique coset Stab;,, above. On the other hand, each coset Stab, maps to unique element T; E X under the Orbit-Stabilizer paradigm. We construct f by setting f(o) fzx It is easy to verify that ff indeed satisfies the requirements of the commutative diagram above, thereby verifying that is a legitimate lift of / from X to Sn, as desired.
We conclude this section with theoretical analysis of how the group action homogeneous space X decomposes X into a disjoint union commutator orbits.
Lemma C.1. Let the group G act transitively on the homogeneous space X. Let f X R. with the
lift f G - R such that f f π, where क : G + X is the canonical projection map. Then f being conjugation invariant under is equivalent to f being invariant under the induced action of [,, G on X, where [G, G) is the commutator subgroup of generated by {gg [g
h]]= = -hg-gg-hh 11-1 g, E G).
Proof. Fix 2o E X. We define f(g) = flg ro) for g E G. f is conjugation invariant if f(h x0)yg, h E G. Writing
(ghh-11) = [00==[(()] [(h)Vg, h E G. In terms of f, we have [igh--1. & = h. -.. we may write -i --- (x))Vg h E G, that is, f(gg. -)) f(x) Vg, h E G, where [g. h ghg-ghhhhg h is the commutator of and h. Thus, f is conjugation invariant implies that of is |G, G] invariant. It is easy to see that we can reverse this argument to obtain the converse implication.
To summarize, the full group G acts transitively on the homogeneous space X, enabling a lift of the function f to function ff on G. This function being conjugation invariant on G amounts to the function f being invariant to the induced action of the commutator subgroup [G, GJ on X. We may view this as the homogeneous space X being partitioned into [G, G)-orbits, whereby f is constant on each [G, -rrbi...
For any group G, the commutator subgroup [G, G] is the smallest normal subgroup N of G such that G/N is abelian. In some sense, [G, G] captures all the non-abelian attributes of G.
Commutators are well-studied objects in group theory. For example, it is known that the commutator of the symmetric group Sn is the alternating group A,, For the dihedral group D2n, which is generated by a reflection x and a rotation satisfying the relations x² y" = Zyz = y the commutator [G, G] is the cyclic subgroup generated by y².
D COMPACT VS NON-COMPACT GROUPS
We emphasize that, in the present work, we focus on the case of compact groups; finite groups trivially belonging to that category in particular. Compact groups are, sense, a natural point of departure for investigations such as ours for an array of reasons. On one hand, compact groups (such as rotations or permutations) provide some of the most fundamental models for learning under non-abelian group actions. On the other hand, compact groups allow for very concrete and well- understood representation theory and character theory, as outlined in the main text. However, the action of non-compact groups does arise symmetries in many interesting applications. Of course,
4

---

Under review as a conference paper at ICLR 2022
for locally compact abelian groups, we have elaborate theory of commutative Fourier analysis on groups, as discussed in the main text (also c.f. (Rudin [962); a ready example being provided by the commutative action of the group of real numbers (or that of R in general) in many natural learning set ups. A natural application of locally compact non-ahelian groups is accorded by the group of Euclidean isometries (denoted E(n) ISO(n)), generated by translations and rotations acting on Euclidean space. In more advanced physical applications, depending on the energy scale and relativistic effects involved, it also of interest to investigate the action of the Galilean group or the Poincare group (c.f. (Amol'd d 2013 Nadjafikhah & Forough, 2007] Tung 1985)). While the representation theory and the character theory of general classes of non- anncompact non-abelian groups poses a formidable mathematical challenge, the investigation of specific groups relevant to applications opens a natural direction for future work.
E GROUP REPRESENTATIONS, IRREDUCIBLE CHARACTERS AND FOURIER ANALYSIS
E.1 GROUP REPRESENTATIONS IRREDUCIBLE CHARACTERS AND PETER- WEYL THEORY
We provide here the very broad contours of only a few aspects of the deep theory of group repre- sentations Simon (196)., focussing ingredients that would be germane to our approach. We will consider p be matrix representation of G. That is, p any I, y E G; and p(e) = I, where is the identity element of G and I is the identity matrix. The character Xp of p the function X - C defined by x(x) = tr(p(x)). We call dp the order of P Xp. We say that is reducible if it decomposes into a direct sum of smaller representations as
Cd p(zy)
p(z)p(y) for
(1)
0
p(x) (p'((((pp))) (p2(())) Q-1
Vr E G for some invertible matrix
0
P2(x)
Q E Cd, which is independent of x. Otherwise, say that p irreducible. If is irreducible representation, we say that X, an irreducible character. Since tr(T AT) tr (r),), it is evident that Xp is class function. By the celebrated Peter- Weyl theorem (Simon 1996), the set of irreducible characters form an orthonornal basis for the space of square integrable class functions.
E.2 REPRESENTATION THEORY AND NON-COMMUTATIVE FOURIER ANALYSIS.
Classical Fourier analysis, in its simplest avatar, entails that given a function f S C, may decompose f f(x) Σx f(k)e with the Fourier coefficients being defined as undertake Fourier analysis may decompose f as f(x) - f (())x(==)ddddd ddi((), with f(x) = Sc
f(k) 2r 2T (z))-ikzdd dx. Representation theory allows
groups If
G + C (where G is a locally compact abelian group with Haar measure μ4), we
here where ranges over the the space of irreducible characters of Gi (equalling this case the so-called Pontryagin dual G). It is known that the irreducible representations of an abelian group are all one-dimensional,
so each f(x) is still scalar.
If G is non con-abelian but is compact, then the set of irreducible representations, also denoted as R(G). known to countable, and the representing matrices p may be taken to be unitary matrices. Given function f:: G C, we may decompose f as
Σ d,tlf(e)p(==")) with f(e) = / f(x)p(2)dp(z)) PER(G)
f(x) ((G)
(3)
may be noted in this case that each Fourier coefficient f(p) is a matrix, leading to the notion of non-commutative Fourier analysis stemming from the fundamentally non-commutative nature of matrix multiplication.
E.3 PLANCHEREL'S S THEOREM AND BAND-LIMITED FUNCTIONS.
In classical Fourier analysis, Plancherel's 's Theorem tells us that the Fourier transform preserves energy; namely, - (2r = -x (2 Since the sum on the right is finite, [f((k)2 + as k xo. Thus, f(x) is well-approximated by Et=kp e( for sufficiently large ko. This is akin
5

---

Under review as a conference paper at ICLR 2022
to band-limiting f, a device that is extremely useful in signal processing and many other areas of applied mathematics. the case of compact groups, is known that the non-commutative Fourier transform f + f defined above satisfies a non-commutative Plancherel's theorem. Indeed,
mCG) Ia ((())
Σ PERAG)
(4)
[M()]}
Since the sum the right of (4 is finite, (If(p) 0 as dp - xc. Thus, f(x:) is well- approximated by д[द) Ed,5,, dntr(f(p)p<x= for sufficiently large ko, leading to a notion of non-commutative bandlimiting for functions defined on non-abelian groups.
F EXPERIMENTS
Using the ideas in Sec. 4.3, we implement several numerical experiments to show how neural networks with small alphabet be used approximate various class functions. Our experiments are implemented using TensorFlow (Apache License 2.0), Keras (MIT License) [Aaai et al.] (2013); Chollet et al. (2015) and SageMath (GPLv3) Stein et al. (2021). Tensorflow and Keras was used to train our models. SageMath was used to compute the irreducible characters of S30-
F.1 LEARNING CLASS FUNCTIONS ON S,
Since the conjugacy classes of Sn are canonically labelled by partitions class functions S, can be realised as functions on P(n). Set n = 30. There are 5604 partitions of 30. We generate 100 class functions on S30 by taking Gaussian linear combinations of 10 irreducible > are the 251", 252"d 260 elements of P(30) in the lexicographic order A Our training data comprises 1400 (~25% of [P(30)) function evaluations (A, (A)),, where the partitions À are sampled uniformly at random from P(30). To approximate this, we train fully connected neural network with 3 hidden layers of width 180, 120 and 50 respectively. The input layer consists of the 50 irreducible characters (300) (29.1),. ..... x (22,6,1111, x (189); these are the irreducible characters corresponding to the first 49 elements of PP30) in the lexicographic order, on top of the one-dimensional sign character (19)), The SELU non-linear activation function and Gaussian kernel initializer is applied throughout. We minimize the squared error loss (MSE) with L2 regularization parameter a 0.001 using AdaMax Kingma & Ba (017).
characters x (1.1112211111111 xx (18.1111111)) (18, 4, 2, 1,1,11, > > 3,8,3,,,,1,,11,,, (1..1111.., (18, 4, 1,
As benchmark, we train a linear regression model with 100 input alphabets (30), xx (29.1) x (20.9.1), () these are the irreducible characters corresponding to the first 99 elements of P(30) in the lexicographic order plus the sign character (19)), Gaussian kernel initializer used and we minimize the squared error loss using Adam Kingma Ba (2077).
Note that we apply the same hyperparameters (chosen to ensure reasonable convergence) for each of the 100 class functions that we train. Our neural network was trained over 200 epochs using a batch size of 100 for each class function. The linear regression model was also trained over 200 epochs using a batch size 100. Our models are evaluated using 10-fold cross-validation.
In the scatter plot of Figure I each point corresponds to the performance of our models on fixed class function, with the y-axis representing the mean MSE over 10 folds and the r-axis representing the corresponding standard deviation. Taking the mean MSE over 10 folds as representative for each scatter point, we obtain the histogram in Figure [ We display the average of the histogram in its legend. Note that normalized each of the 100 class functions f that the mean of squares over the 1400 instances of fA) is equal to 1.
We find that the performance of the neural network is far superior to the performance of linear regression model with double the size of the alphabet. The mean MSE over 100 class functions trained for linear regression is 5.10 times higher than that for the neural network.

---

Under review as a conference paper at ICLR 2022
Symmetric groups class function learning performance
Symmetric groups class function learning performance
0.004107
Neural Network
Linear Regression mean 0.020938
Regression
ooer 10 tocck of MEF
Freuudcc
0.
0.0
0.1
0.2
0.3
0.
0.0
0.
0.4
0.6
08
10
12
Vean HSE ever fdids
Standard Deviation over 10 fotes
Figure 1
F.2 LEARNING CONTINUOUS CLASS FUNCTIONS ON SO(3)
This experiment was described briefly in Section 6. We provide the full details here. Let Xj be the irreducible character corresponding to the (2j + 1)-dimension irreducible representation Pj of SO(3) (see Section 5.1). Then, Xj is the real-valued function x3 (in((25+1)8822) for 0 S 3 S (note that class functions SO(3) depend only
slu(0/2)
single angle (3).
We generate 100 class functions f on SO(3) by taking Gaussian linear combinations of 10 high order irreducible characters X50, X51 X59. Our data comprises 24000 function evaluations (g- (ar, 7) was drawn uniformly at random from [0, 2T] x [0, ा x [o, 2m]. We split our data into train, validation and test sets with 20000, 2000 and 2000 points respectively, fully connected neural network (ConjInv) with hidden layers of width 100, 50 and 20 respectively fit the train set over 180 epochs using batch size of 1000. The input layer consists of the 11 lowest order irreducible characters Xo. X X10 of SO(3) (see Sec. 4.3). The ReLU non-linear activation function used at every layer except the last. Gaussian kernel initializer applied throughout, We minimize the squared error loss (MSE) with L2 regularization parameter 5 x 10-4 using Adam Kingma & Ba (0077) with learning rate 10 3 The hyperparameters were tuned according to the validation set.
(or, 8, ( [(8),, where
Our first benchmark is a fully connected neural network with 6 hidden layers (DeepEuler) of width 150, 120, 80, 60, 30 and 10 respectively. The input layer consists of the three Euler angles (a. 3, 7). DeepFuler is fit to the train set over 130 epochs using a batch size of 1000. The ReLU non-linear activation function is used at every layer except the last. Gaussian kernel initializer is applied throughout. By tuning hyperparameters according to the validation set, we optimize DeepEuler using Adam Kingma & Ba (017) with learning rate x 10-" subject to L2 regularization parameter 3 x 10-12
As second benchmark, linear regression model Regression with 33 input alphabets Xo. XI....,X3: is fit to the train set over 100 epochs using batch size of 500. Gaussian ker- nel initializer used. By tuning hyperparameters according the validation set, we optimize Regression using Adam Kingma & Ba (211)) with learning rate 3 x 10-3 and L.2 regularization parameter 16
The three models are evaluated on the test set. We compare their log losses in Figure 2 Positive values our histogram represent instances when ConjIny outperforms its benchmark. Observe that when compared against Regression, ConjIny has superior performance 100 out of 100 times. On the other hand, ConjInv outperforms DeepFuler histograms, conclude that average, the mean squared error loss for Regression and DeepEuler are e 4.30 73.7 and 2.77 15.8 times that of ConjInv respectively.
out of 100 times. By taking the average of the
F.3 LEARNING DISCONTINUOUS CLASS FUNCTIONS ON SO(3)
We provide the full details to the experiment described in Section Let Xj be the irreducible character of SO(3) (see Sec. F2
7

---

Under review as a conference paper at ICLR 2022
DeepEuler vs Conjinv (continuous)
Regression vs Conjinv (continuous)
12
mean 2.70486
15.0
mean 4.303261
10
12.5
Frequency
Frequency
10.0
7.5
5.0
2.5
0.0
3 4
1
3
6
log( MSE((eepEuler) [SE[(on))nn)]
logí MSE(Regression) MME((Conjnvv) ]
Figure 2
DeepEuler Conjinv (discontinuous)
Regression Conjinv (discontinuous)
692083
15.0
222852
12.5
12.5
Frequency
10.0
Frequency
10.0
7.5
7.5
5.0
2.5
2.5
0.0
0.0
1.5
20
2.5
3.0
3.5
4.0
4.5
1.25
225 2.50 2.75 3.00 logt MSE(Regression) MSE((onjiny)) ]
1.50
1.75
2.00
logi MSE(DeepEuler) MSE(Conjinv)]
Figure 3
100 discontinuous class functions f on SO(3) are generated by taking Gaussian linear combinations of some binary valued indicator functions 1o. 1,...., 19, where
{1 0. 3 $ 0.1mk + 0.12m,
(,,7),,7)
otherwise.
Drawing 24000 instances of g (a, B, 7) uniformly random from [0. 2n m) [0, 2mr], obtain 24000 datapoints of the form (g. (()). We split our data into train, validation and test sets with 20000, 2000 and 2000 points respectively. We fit ConjIny from Sec. F.2 to the train set over 180 epochs using a batch size of 180. By tuning the hyperparameters according to the validation set, we minimize the mean squared error loss with L.2 regularization parameter 10 using Adam Kingma & Ba 2017) with learning rate 10
Just like in Sec. F22 our first benchmark is DeepEuler, which is fit the train set over 180 epochs using a batch size of 2000. By tuning hyperparameters according to the validation set, we optimize DeepEuler using Adam Kingma & Ba (017)) with learning rate x 10-2 subject to L2 regularization parameter 10-18.
We also benchmark against Regression, which fit the train set over 100 epochs using batch size of 500. By tuning hyperparameters according to the validation set, we optimize Regression using Adam Kingma (2017) with learning rate 3 x 10-3 subject 1.2 regularization parameter 10
The three models are evaluated on the test set. We compare their log losses in Figure 3 Positive values in our histogram represent instances when ConjInv outperforms its benchmark. Observe that when compared against DeepEuler and Regression, ConjIny achieves superior performance 100 out of 100 times. By taking the average of the histograms, conclude that average, the mean squared error loss for Regression and DeepEuler are 2.22 = 9.2 and 2.69 = 14.7 times that of ConjInv.
8

---

Under review as a conference paper at ICLR 2022
Discontinuous SU(3) class function
NN5 2.361959
Linear 378
40
Frequency
30
20
0
100
10a
10a
10a
Mean Squared Error
Figure 4
F.4 LEARNING DISCONTINUOUS CLASS FUNCTIONS ON SU(3)
Let X be the irreducible character corresponding to the irreducible representation D(p.q) of SU(3) (see Section 6.2). Then, x is the complex-valued function X (0,
e(S(2pt))
D E D ( siul(k- for -2x S Φ S 2n and -3x S 0 < 3v. Since
sin(s/2)
Keras does not support complex valued data types, we use the Complex-Valueee Neural Networks library Barrachina (202T) work with class functions on SU(3).
We generate 100 discontinuous class functions on SU(3) by taking Gaussian linear combinations of 25 binary valued indicator functions Ix, for 0 S k, I 4, where
if - 3x + 1.2kT 0 -3 1.2kT 1.32 and
10,(00, の)
2T 0.8 S S + 0.8lm + 0.88
otherwise.
Our training data comprises 8500 function evaluations (0, o. f00 6)), where (0, ø) drawn uniformly at random from -T, 3T] x [-2n, 2 To approximate this, we train fully connected neural network with hidden layers of width 180, 150, 100, 60, 35 and 10 respectively. The input layer consists of the 25 irreducible characters x for S P. Σ 4. The ReLU non-linear activation function is applied throughout, except in the last layer where the activation function takes the absolute values of complex numbers to provide a real-valued output for the purposes of training. We minimize the squared eиror loss (MSE) with L2 regularization parameter 10-8 using AdaMax Kingma & Ba (207))
As benchmark, we train linear regression model with 49 imput alphabets x for S S.9ST and an activation function that takes the absolute values of complex numbers to provide real-valued output for the purposes of training. We minimize the squared error loss with 1.2 regularization parameter a 10-9 using AdaMax Kingma & Ba (2077).
Note that we apply the same hyperparameters (chosen to ensure reasonable convergence) for each of the 100 class functions that we train. Our neural network was trained over 100 epochs using batch size 500 for each class function. The linear regression model was trained over 300 epochs using a batch size of 250. Our models are evaluated 1500 unseen datapoints (0, Φ) drawn uniformly at random from [- 3T, 3T) x 1-2m, 2T..
Recording the squared error loss (MSE) of our two models these 100 class functions, obtain 200 entries for the histogram in Figure 4 Our neural network performs 160 times better than linear regression with almost double the size of the alphabet, achieving MSE of just 2.362 compared to 378.1.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath

---

Under review as a conference paper at ICLR 2022
Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fermanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. httpstss: /www tensorf org/ Software available from tensorflow.org.
Vladimir Igorevich Amol'd. Mathematical methods of classical mechanics, volume 60. Springer Science & Business Media, 2013.
J Agustin Barrachina. Complex-valued neural networks (evnn), January 2021. URL https:
//doi. 5281/2enocs 4452131
Christopher Bowman, Maud De Visscher, and Rosa Orellana. The partition algebra and the kronecker coefficients. Transactions of the American Mathematical Society, 367(5):347-3367, 2015.
François Chollet et al. Keras. attps://keran 1o, 2015.
Morton Hamermesh. Group theory and its application to physical problems. Courier Corporation, 2012.
Gordon Douglas James. The representation theory of the symmetric groups, volume 682. Springer, 2006.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Blaine Lawson Jr. Foliations. Bulletin of the American Mathematical Society, 80(3):669-41 1974.
Mchdi Nadjafikhah and Ahmad-Ran Reza Forough. Galilean geometry of motions. arXiv preprint arXiv:0707.3195, 2007.
Walter Rudin. Fourier analysis on groups, volume 121967. Wiley Online Library, 1962.
Barry Simon. Representations of finite and compact groups. Number 10. American Mathematical Soc., 1996.
A. Stein al. Sage Mathematics Software (Version 0.6.2). The Sage Development Team, 2021. http: hwwp//wwww...////...t sagemath. org.
Vasu V Tewari. Kronecker coefficients for some near-rectangular partitions. Journal of Algebra, 429: 287-317, 2015.
Wu-Ki Tung, Group theory in physics, volume 1. World Scientific, 1985.
Gerard Walschap. Metric structures in differential geometry, volume 224. Springer Science & Business Media, 2012.
10


Reviews:
[{"review_id": "oeOd06OXgeb", "reviewer": "Reviewer_zG1H", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: By using the theory of characters and class functions, they have created a new method for learning class functions.\n\nWeaknesses: \n-The fact that the class of characters must be fixed in order to construct the algorithm.\n-The point that when the group is not a finite group, the set of characters is not finite and therefore not sufficiently expressive.\n-What seems to be a lack of applications for key machine learning tasks such as graphs and point clouds.\n\nThis method is a so-called feature extraction type algorithm. The main problem is that when you try to implement this algorithm by yourself, you have to calculate the characters by yourself, and the set of characters is not finite in general. In recent years, it has become desirable for deep learning to automatically learn the character part of this method and construct a model. Isn't it possible to define a layer that controls the characters and automatically learn the necessary characters for the desired function? ", "summary_of_the_paper": "This paper provides an algorithm for learning class functions that are invariant to special group actions.", "summary_of_the_review": "By using the theory of characters and class functions, they have created a new method for learning class functions.\nHowever, the scope of application is limited and its usefulness is somewhat questionable, so I judged it not worthy of high evaluation.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "eYy0bhSEyb", "reviewer": "Reviewer_5x3M", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\nThe paper addresses learning with invariances which is an important topic, and a white-hot one. Looking at class functions is natural and the paper does a good job of reviewing the various situations in computational sciences where class functions arise. The authors convincingly argue that higher-order characters can be obtained as functions of low-order characters and that as a consequence neural networks may be able to effectively learn complicated class functions. The paper is well written and easy to follow, it does a good job summarizing the requisite group theory, and the numerical experiments indicate the potential of the proposed strategy.\n\n### Weaknesses\n\n- The strategy proposed by the authors follows a standard recipe borne out in numerous machine learning and signal processing contexts: compute a set of _fixed_ invariant features (with a suitable notion of invariance) before applying a standard learning model (here a neural network). The only technical content in the manuscript is on pages 7 and 8. There is absolutely nothing wrong with simplicity, brevity, and strong introductions (to the contrary), but in this case I cannot escape the impression that the idea is good but the paper needs a lot of work (either on the side of theory, or the numerics, or both). In particular, the motivations from the introduction were not at all vindicated in the experiments.\n\n- The two theorems on page 7 state that the polynomial algebras of characters of SO(3) and SU(3) are generated by a few irreducible characters. This fact is not surprising to people familiar with group representations (I would like to say that it is known although (perhaps) not commonly written in this exact form. It certainly follows directly from (3) in the case of SO(3) and (5) for SU(3).) It is still a good motivation for applying neural nets to a small set of features obtained from low-order irreducible characters, but one would hope that this discussion will be taken much further. For instance, for common class function, when can we expect good approximation properties of this scheme? This would require looking into how the used neural networks generate high frequencies from low frequencies (in the context of irreducible characters) or some other strategy to establish strong approximation statements.\n\n- The introduction describes several exciting motivations but I find these descriptions somewhat disconnected from what could and should be learned. The numerical experiments on page 8 only involve direct synthetic constructions of class functions and tackle none of these motivating applications. \n\n- In the motivation via image alignment, where do you see your scheme playing a role? The quantity $\\mathcal{M}_{x, y}$ is indeed a distance and not a class function itself; $\\tilde{f}$ _is_ a class function but it can typically be computed exactly and very fast using FFTs on groups or homogeneous spaces. Can you provide a related numerical example, even if stylized, where your strategy can improve things?\n\n- In the motivation via QAP, you suggest that learning $f$ gives a stopping algorithm. Can one in general hope to learn $f$? What is its complexity class? Also, for any reasonable $\\epsilon$, why would it be possible to do well using gradient descent on this very non-convex problem?\n\n- Figures 1 and 2 have no caption which makes it hard to interpret them.\n\n", "summary_of_the_paper": "This paper proposes a strategy to learn class function on groups (and by extension on homogeneous spaces). The paper is motivated by applications in inverse problems and image processing (e.g. particle alignment in CryoEM) as well as integer programming (e.g. the quadratic assignment problem). The authors note that irreducible characters form a basis for square-integrable class functions and then apply a neural network on a set of invariant features chosen as low-order irreducible characters rather than directly on the input, which naturally results in a conjugation-invariant function. They argue that the neural network (thanks to the nonlinear activations functions) can generate the needed high-order characters. The obtained invariant architecture is then applied to several toy problems with synthetic data.\n", "summary_of_the_review": "This paper proposes a nice idea: to learn class functions by first applying a feature transform, where features are chosen to be invariant to conjugation (in particular, low-order irreducible characters), and then processing those by a neural network. The authors justify this by noting that irreducible characters form an orthobasis for the space of square-integrable class functions, and that (by their algebraic structure), high-order characters can be generated from a few low-order characters. The paper is well written but at this conference I would expect to see much more technical content, stronger results, more convincing numerical experiments. I think that this can become a strong paper but the current version records a nice idea with solid potential and presents some initial numerics.\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cZnNSZ5-M74", "reviewer": "Reviewer_Y8tG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The starting point for this paper is recent work on constructing models that respect some task-specific symmetries, as encapsulated by equivariance and invariance constraints, most often to the action of a (locally compact) group. The focal point for the paper, however, is an important class of observables captured by class functions: functions on a group that are constant over conjugacy classes, and thus by extension the paper has relevance to problems that involve learning conjugation invariant functions. Such functions can also be lifted easily to spaces over which the group acts transitively -- a situation more common in problems of interest in machine learning. The conjugation action can be seen as affecting a change of basis and has close connections to a special case of non-commutative Fourier analysis, which is realized by an orthogonal basis of irreducible characters. \n\nOne setting in which invariance to such actions arises naturally in ML is covered in an averaging paradigm, encapsulated in proposition 2.1. This is illustrated by various examples quite crisply. Some examples include image alignment in the challenging case when two images lie on a sphere; the QAP; multi-object tracking; an important statistic for comparative analysis of rankings. In particular, it is shown that these problems rely crucially on conjugation invariance and thus on modeling the class function of interest. The paper then makes the claim that it is important to approximate such class functions efficiently since they are clearly relevant to many problems of interest and focuses on it in the sequel. \n\nThe paper capitalizes on the notion that irreducible characters are closed under polynomial combinations. This has the implication that using polynomials of a few irreducible characters (of lower order) one can express characters of considerably higher order. The canonical polynomial algebra structure on the characters is handed over by the theory of tensor products of group representations and involves using the Clebsch-Gordan coefficients. As might be apparent, this hints at a general paradigm for approximating general class functions via non-linear, polynomial combinations using a small alphabet of characters. The algorithm is stated in section 4.3. It consists of considering a small number of irreducible characters of the group as input and a set of samples with the group elements and the class function of interest as the label. If the number of irreducible characters is w, then for each example, we construct a w dimensional vector of characters. This w dimensional vector becomes an input to the neural network. For any new input, we first find the w dimensional vector, do forward propagation, and output the result. It is also shown that for groups such as SO(3) and SU(3) a very small number of characters are sufficient to generate all the characters, leading to a good approximation of general class functions. This is illustrated in sections 5.1 and 5.2. Numerical experiments are shown to corroborate the claim. \n\nIn my view, the paper presents an interesting direction of research. I found the initial parts of it exciting and enlightening. It indeed hits on an important structure in various machine learning problems that are rarely attacked from the point of view of approximating conjugation invariant functions (although they do appear implicitly in many forms). It must be noted that some problems do use some of the ideas in an implicit form. For instance, the early spectral graph convolution methods can be seen as a special case of convolution with a class function (thus every Fourier component is a sum of characters), the rest of the network can be seen as taking combinations of these outputs. Work on using invariant polynomials (such as by Ward Haddadin are also relevant). However, these works don't directly deal with the scenario that the paper deals with. This paper can also be seen as extracting invariant features, which should be useful for some task of interest. \n\nHowever, while interesting, the paper needs to pick one of the problems that are stated as examples, and show that the method used here leads to good performance experimentally -- I have a feeling that it might be difficult to get things to work on a problem like solving the QAP. While I liked the paper overall (especially its general discussion in the first half), I think it is not quite ready for publication without extensive experimental results. Only showing that the class function is approximated well by a non-linear network is great, but is not surprising due to the underlying theory. The paper can be made quite strong, and become a general and useful reference if this procedure is shown to be crucial for solving one of the problems listed.", "summary_of_the_paper": "The paper first makes the case that learning conjugation invariant functions is of interest in many machine learning problems, stating in a general form in which they appear. It then presents a simple method, using a MLP, for approximating such functions efficiently using a small number of irreducible characters. This capitalizes on the notion that irreducible characters are closed under polynomial combinations. Thus, using polynomials of a few irreducible characters (of lower order) one can express characters of considerably higher order. It is shown that the method proposed can approximate class functions of interest well numerically. ", "summary_of_the_review": "The paper presents an interesting perspective of learning conjugate invariant functions. It provides a simple method for the non-linear approximation of class functions. The attendant discussion for many problems of interest is also valuable and useful. The paper does not propose a new theory -- it crisply teases out the importance of building in such invariance to many problems of interest. While valuable, it needs validation on one problem of interest. I think the paper has the potential to be a strong and valuable contribution. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "_zKzRLDR7rR", "reviewer": "Reviewer_qL2S", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presentation of the paper could be significantly improved. In fact, there is no \"Introduction\" section that describes the context of the problem setting and introduces the contributions of this work at a high level. I don't think it's a good idea to start a paper directly with almost two pages of related works without first introducing the context properly. \n\nOverall, I find the paper hard to follow. Although I tried to understand the contributions of this paper at my best effort, I couldn't properly evaluate its contributions. I understand this may be due to my limited knowledge of group theory, but I also think the authors should try to present the paper in a way that a broad audience in the machine learning community could understand and appreciate. Hence, I would vote for rejection for now, but I encourage the authors to resubmit to the next venue after improving the presentation of the work. \n", "summary_of_the_paper": "I have to confess that I was not able to understand the main thesis or contributions of this paper. \n", "summary_of_the_review": "I didn't follow the main thesis that this paper tries to convey, and I guess this may happen to a broad audience of the general ML community as well. In my opinion, the main goal of the publication is to spread the idea so that more people in the community could appreciate it. From this perspective, I have to vote for rejection for now.  ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "A9Gbbtdm4bu", "reviewer": "Reviewer_E1Av", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The paradigm proposed in the paper is very interesting, and I liked the manuscript, especially the Appendix, which explains the mathematical concepts in an easy-to-understand manner.\nPersonally, I feel the paper very interesting and instructive, and I think it should definitely be published somewhere.\nOn the other hand, as the authors mentioned in 7 Discussion, the paper does not mention the application of the proposed paradigm around machine learning field.\nAlso, it was not clear how the proposed paradigm would solve the problem of Image Alignment, which was mentioned in the paper as a possible application.\nThese facts may indicate that this paper is a little different from the scope of this conference.\nTherefore, it seems inappropriate for this paper to be accepted for the conference.\n\nIn addition, the main text of the paper, especially the introduction part, was difficult for me to understand how each paragraph relates to the preceding and following paragraphs.\nAlso, the description using only sentences hindered my understanding.\nIt would be desirable to use equations and figures to make the description more understandable to people from various fields in this conference.", "summary_of_the_paper": "In this manuscript, the authors develop a DNN paradigm that learns functions on groups as polynomials using canonical tracial class functions as an orthogonal basis for class functions called irreducible representations.\nSince the basis constitutes a nonlinear coordinate system, it has the potential to efficiently handle complex symmetries.\nThe paper shows analyticaly and numericaly that for simple systems such as SO(3) and SU(3), the proposed paradigm has high expressive power with few bases.", "summary_of_the_review": "As the authors mentioned, the paper does not mention the application of the proposed paradigm around machine learning field.\nAlso, it was not clear how the proposed paradigm would solve the problem of Image Alignment, which was mentioned in the paper as a possible application.\nThese facts may indicate that this paper is a little different from the scope of this conference.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviews received for this paper raise several critical concerns to which the authors have not provided a response. Thus, in its present form, the paper is not ready for publication.
Decision: Reject