Universality of Group Convolutional Neural Networks Based on Ridgelet Analysis on Groups
Authors: Sho Sonoda
Isao Ishikawa
Masahiro Ikeda
Venue: NeurIPS 2022 Accept (2022)
Keywords: group convolutional neural network (GCNN)
universal approximation
group equivariance
ridgelet transform

Abstract: We show the universality of depth-2 group convolutional neural networks (GCNNs) in a unified and constructive manner based on the ridgelet theory. Despite widespread use in applications, the approximation property of (G)CNNs has not been well investigated. The universality of (G)CNNs has been shown since the late 2010s. Yet, our understanding on how (G)CNNs represent functions is incomplete because the past universality theorems have been shown in a case-by-case manner by manually/carefully assigning the network parameters depending on the variety of convolution layers, and in an indirect manner by converting/modifying the (G)CNNs into other universal approximators such as invariant polynomials and fully-connected networks. In this study, we formulate a versatile depth-2 continuous GCNN $S[\gamma]$ as a nonlinear mapping between group representations, and  directly obtain an analysis operator, called the ridgelet trasform, that maps a given function $f$ to the network parameter $\gamma$ so that $S[\gamma]=f$. The proposed GCNN covers typical GCNNs such as the cyclic convolution on multi-channel images, networks on permutation-invariant inputs (Deep Sets), and $\mathrm{E}(n)$-equivariant networks. The closed-form expression of the ridgelet transform can describe how the network parameters are organized to represent a function. While it has been known only for fully-connected networks, this study is the first to obtain the ridgelet transform for GCNNs. By discretizing the closed-form expression, we can systematically generate a constructive proof of the $cc$-universality of finite GCNNs. In other words, our universality proofs are more unified and constructive than previous proofs.

Universality of Group Convolutional Neural Networks Based on Ridgelet Analysis on Groups
Sho Sonoda
Isao Ishikawa
Masahiro Ikeda RIKEN AIP
RIKEN AIP
Ehime University
sho sho.sonoda@riken.p jp
ishikawa isao. ax0ehime-u.ac.jp
masahiro wiw.iiioiiieearikee...
Abstract
We show the universality of depth-2 group convolutional neural networks (GC- NNs) in a unified and constructive manner based the ridgelet theory. Despite widespread use in applications, the approximation property of (G)CNNs has not been well investigated. The universality of (G)CNNs has been shown since the late 2010s. Yet, our understanding on how (G)CNNs represent functions is incom- plete because the past universality theorems have been shown in case-by-case manner by manually/carefull assigning the network parameters depending on the variety of convolution layers, and in an indirect manner by converting/moddis the (G)CNNs into other universal approximators such as invariant polynomials and fully-connected networks. In this study, we formulate a versatile depth-2 con- tinuous GCNN Shy] as a nonlinear mapping between group representations, and directly obtain an analysis operator, called the ridgelet trasform, that maps given function f to the network parameter ry so that ST>] = f. The proposed GCNN covers typical GCNNs such as the cyclic convolution on mulii-channee images, net- works on permutation invariant inputs (Deep Sets), and E(n) eqquivaria networks. The closed-form expression of the ridgelet transform can describe how the network parameters are organized to represent a function. While it has been known only for cally-connected networks, this study the first to obtain the ridgelet transform for GCNNs. By discretizing the closed-form expression, we can systematically generate a constructive proof the ce-universality of finite GCNNs. other words, our universality proof' are more unified and constructive than previous proofs.
1 Introduction
In the research field of geometric deep learning [1. group convolutional neural networks (GCNNs) have been developed to capture the inductive bias behind variety of datasets such as sets and point clouds 2 3 graphs [4] 5), manifolds, groups, and homogeneous spaces 668 Despite the rapid growth of diversity, the appreximation property of CNNs is less investigated than that of fully-connected neural networks (FNNs). To this date, several authors have shown the universality of (G)CNNs. That is, they can approximate some class of continuous maps with any precision [6] These studies are still limited because the proofs are shown (1) in case-by-case manner by manually assigning the parameters for a network to approximate a given function f. which means that once the network architecture is modified, then need to reassign the parameters from scratch, and (2) in an indirect manner by converting/modifying the (G)CNNs into other universal approximators such as invariant polynomials and FNNs, which means that know only indirectly about (G)CNNs.
The approximation property of FNNs has been investigated in the 1990s, with gradually increasing the resolution of proofs from abstract to concrete, starting from purely existential proofs based on theorem [17] and the Stone-Weierstre Weierstrass theorem [18), indirect proofs based on the
the
Fourier transform [9 20 the Radon transform 21 22
B-splines 23 24 to more constructive
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

proof's based on the integral representation (25, ridge functions [26]. and the ridgelet transform 27 29. For deep-ReLU-FNNE further upproximation properties have been investigated [30 in the 20s0s. In this context, (G)CNN studies are at the stage of case-by-case and indirect proofs. (See $ 6. for more details).
In this study, we show the universality of depth-2 GCNNs by devising general notion of group convolution and developing the ridgelet transform for GCNNs-an an analysis operator that maps given function f to the weight parameter y in a single hidden layer of a neural network. Consequently, our universality proof is more unified and constructive because our GCNN covers a wide range of typical GCNNs, and the ridgelet transform can describe how to assign the network parameters.
In the following, describe the formulation of GCNNs overview main contributions.
Typical Convolution Layer for Images. Given an my mz-dimensional nun -canneel input image æ E IR XPim, typical convolution layer with wi wz-dimensional 7in X nout Tou -chaneel filter a E IR (R X1e2 Xnin x N and -hanneel bias b n followed by an elementwise activation function -R- + R and the aggregation with output coefficients E IR nout is given by
Poot
Ain
Sla, b. (i))((t))
Σ do
ΣΣ>
Σ
Opg popitp -69 66)
for each pixel at (i.j) E [m] w + 1] x [m2 - W2 + 17.
For technical reasons, we assume that the output channels (indexed by l [Mowr] are aggregated soon after the activation function, which may be slightly different from an ordinary formulation of CNNs. but we can understand this as part of the subsequent layer.
In the standard formulation of GCNNs, multi-channel image is understood function on a group G or a homogeneous space G/H, such as a product group G = Z x Zimz of cyclic groups Zm, := Z./m,Z Z (i 1, 2). (More geometrically, Cohen and Welling (33 phrased it as 'a section of a fiber bundle"). .) The convolution in the pixel directions (i,j) reformulated as a group convolution with respect to the product group, and the inner product in the channel direction is understood as the convolution with respect to the trivial action of G on a 'fiber' Riis.
vector-valued
The Integral Representation S[7] of Group Convolution Layer. Let G be an arbitrary group, a R - R be an arbitrary nonlinear function, X' be an arbitrary Hilbert space feature vector and filter a, and y X' x IR C be arbitrary function, called the parameter distribution. We formulate group convolution layer in an integral form, called the integral representation, as
J aa, b)o x)(g) b)dadb, I X, G.
{l)(()(g))
(2)
JxxR
This is an dufnite-dimensiona reparametrization of depth-2 2 GCNN; namely, each function x a(aa * (g) - b) represents single convolutional neuron, or a feature map of input r parametrized by (a, b), the integration over (a, b) means that all the neurons are assigned, and a single function ?-the purameler distribution parameterizes disrribttion-ppaameeeriies the assignment of each parameters (a, b). Hence, S(1] can be understood as continuous neural nefwork. We note that, however, we put y as a finite sum of Dirac's 's measures such as 7n := - (ata,.be) then the integral representation can also represent a finite model
s(nn(()))))) Σ E x)) b)) xE ge G.
In summary, S[>] is a mathematical model of shallow neural networks with any width ranging from finite to continuous. In particular, the sparsity/low-rankeee of parameters are reflected as the localization/conccnttttioo of parameter distribution 7.
An advantage to use the integral representation is the linearization trick. Whereas a finite network S[yx. is nonlinear in the original parameters (a, b), the integral representation Si1 is linear in the parameter distribution It is first emerged in the 1990s to investigate the expressive power of infinitely-win shallow FNNs 22 25 29); and as well common in today's deep learning theory, for example, to investigate the learning dynamics of SGD such as neural tangent kernel (NTK)
34 (66)
lazy learning 37]. lottery tickets (38) mean field theory [3944] and Langevin dynamics
44

---

The Ridgelet Transform f[ pl b) is a right inverse (or pseudo-inverse) inverse) operator of the integral representation operator S. As an outcome of this study, we have obtained its closed- form expression:
RU; :- f (a) - bjdadb, (a, b) E X x R
where f : X - CO is target valued nonlinear function to be approximated, called a feature map, e E G is the identity element, and p : R - C is an auxiliary function, called the ridgeler function. Provided that f is group equivariant, then under mild regularity assumptions, it satisfies the reconstruction fornsrrratiioooomuuu
S[R[f:
= =
(5)
where ((=-)) denote a scalar product of a and p. Therefore. long the product ((a, p)) is neither 0 nor s0, we can normalize p to satisfy ((a, p)) = so that s]] =
In other words, R and S are analysis and synthesis operators, and thus play the same roles as the Fourier (F) and inverse Fourier (F-1) transforms, respectively. Particularly, the reconstruction formula S[R[J: p]] (o, corresponds to the Fourier inversion formula [F[[]] = S.
An advantage of the ridgelet transform the closed-form expression. Despite the common belief that neural network parameters are a blackbox, the closed-form expression can clearly describe how the network parameters are organized. Previous studies on the CNN universality have also provided several construction algorithms of parameters, but these are only particular solutions for CNN to represent a target function f. and not necessary related to, for example, deep learning solutions. For FNNs, on the other hand, Sonoda et al. 445 have shown that any parameter distribution y satisfying Sh1] = f can always be represented as (not always single but) a linear combination of ridgelet transforms, and they [46] have shown that finite networks trained by regularized empirical risk minimization (RERM) converges
certain unique ridgelet transform. (We note that NTK and the Gibbs distribution can also describe the parameter distribution, but NTK is limited to the kernel regime, and the Gibbs distribution is given only implicitly.) As an application, Savarese et [47] and their followers (4855) have established the representer theorems for Rel.U-FNNY by using the ridgelet transform. Although the parallel results for CNNs have not yet been published, we anticipate that the ridgelet transform could facilitate our understanding of deep learning solutions.
Challenges and Contributions. The closed-form expression of the ridgelet transform has been known only for FNNs, which was discovered in the 1990s independently by Murata 27 Candès [28] and Rubin [29. (We refer to 531 for ridgelet analysis in the 2000s, and [54 56) for more recent results.) One of the difficulties to obtain the ridgelet transform for CNNs is that there is no unique way
to formulate an "integral representation of CNNs". We note that some authors claim the "cquivalence of CNNs and FNNs" (see c.g. [13), but it is somewhat misleading because such equivalence holds only when both CNNs and FNNs are very carefully designed. While FNNs are defined on the Euclidean space RT GCNNs are defined on more abstract space X. For example, since the convolution on the Euclidean space can be written using Töplitz matrices, one could consider a formulation such as Jgaxm xB= (A, ()z AAd where the parameter A is an k x m-matrix. However, this only leads to another ridgelet transform that covers less symmetries G. In fact, it is version of the so-called k-plane ridgelet transform developed in the 2000s (51].
To circumvent this difficulty, we formulate GCNNs as general as possible by dealing with the feature space X, group G, and representation T in a coordinate-free manner. Eventually, we have shown the reconstruction formula for a wide range of GCNNs (as displayed in (). with a relatively simple proof. This study is the first to obtain the ridgelet transform for general class of GCNNs. As an application, we show the co-universality of GCNNs for a general class of group equivalent continuous vector-valued functions in unified and constructive manner.
2 Notation and Basic Terminologies
Notation. For any integer n. > 0, [m] denotes the set [1....,n], For any sets G and K, KC denotes the collection (G - K.} of all mappings from G to K. For any topological space X, C(X) and (X) denote the collections of all continuous functions on X, and continuous functions on X with compact support, respectively. We note that when X is compact, then C(X) Cx(X). For any measure space X and number p E [1, (0) LP(X) denotes the space of p-integrable functions on X.
3

---

2.1
Fourier Analysis on R
We refer
57
58
54
for more details on Fourier transform and tempered distributions (S").
Schwartz Distributions. For any integer d > O, S(IR") and S' (TRA) denote the classes of Schwartz test functions (or rapidly decreasing functions) and tempered distributions on R. respectively. Namely, S' is the topological dual of S. In this study, S'(R) and S(R) are assigned classes of activation and ridgelet functions, respectively. We note that (R) includes truncated power functions max (b, 03 such as step function for
a(b)
1
and ReL.U for
Fourier Transform. The Fourier transform on the Euclidean space I& and its inversion formula has been defined on (at least) three different function classes: L L'(R)), (RR( and S' S'(R)). When f e L' (IE") and f L' (IR"), the inversion formula holds "at every continuous point of ft, which is pointwise equation. When E (RR),,, the inversion formula holds "in L which is not pointwise equation because the equation "f = in L _ is defined as "f(xx) = g(z) a.e.". Similarly, when f 8' (RR",, the inversion formula holds "in S We the third definition for computing the Fourier transform of activation functions E S' (RR such as ReL.U and tanh.
2.2 Group Representation
Let G be group, let X be vector space over field K, and let GL(X) be the general linear group
on X. A group representation T of the group G on the vector space is group homomorphism from G' to (2)) that is, map T G - GL(X); - T. satisfying Tgk Tg ToTh for all g. h G. When G is a topological group, we further assume that the action x X - X:: (g. - T [x] be continuous. Here, X' is called the representation space. We refer to [59] for more details group representation.
Regular Representation. regular representation L is group representation defined on X' as
Let X' be the vector space of all functions G, i.e., X= = KG, The (lefi)
(h) <h) g. h G, x x KC
(6)
In particular, when G a locally compact Haussdorf (LCH) group. then has a (left) invariant measure μu, and we can define the collection (G) of all square integrable functions G with respect the canonical inner product (x,, u) (G) == So x((g) ((g))(g)du(()) for any measurable functions r. C. It known that the regular representation on (T) is unitary representation.
Dual Representation. For any group representation T : G - GL(X), the dual representation T G - GL( a group representation defined the dual vector space X' as the transpose of T 1, that is, g TT 1. When X' is Hilbert space with inner product (, x, then it satisfies the following relation:
LyD>x ge G, x, X.
Matrix Element. For any group representation T' : GL(X), the matrix element (or the matrix coefficient) of T is a bilinear functional fa, on G defined by
fg)((g) a|Ty[=]], g G, X, a X"
(8)
where x is a vector X' and a X" is a continuous linear functional on X. When is Hilbert space, then (identifying X' with X¹) it can be written as
fa) [T]==],a)x)
geG, e,
In the next section, we use this quantity as the generalized form the group convolution.
2.3 Universality
The notion of universality in machine learning can be rephrased the density in mathematics, and thus has several definitions. (See, e.g., 6T). In this study, we show the so-called cc-univesality, one of the standard universalities in the machine learning theory.

---

co-Universality. Let X be a topological space, and let NN be collection of functions (e.g.. neural networks) on X. The cc-univesality of NN is defined as the density of NN in C(X) endowed with the topology of compuct convergence, that is, for any compact subset K = X, continuous function f' C(K), and 0, there exists a function g NN such that
S glæ C(R) :- sup (f() g(x)l < E; =e
(10)
where g| denotes the restriction K.
3 Functions Abstract Hilbert Space X'
We introduce an extended group convolution on X, a uniform norm and the group-equivariance for functions on X, an induced measure and an induced Fourier transform on X, and a projection to Xm-
3.1 (G, -Convolutnn *T x X CG
Definition 1. Let G be group, let X' be Hilbert space with inner product <;,')x over field K, and let T: - GL(()) be representation of G on X. For any a, E X' and G, we define the (G,,))-oovolutionn
(a (a+T x)(g) = (z, TTaT) = (Tg-
(11)
We remark (I) that this is simply a paraphrase of the matrix element a group representation (see the previous section), and (2) that this is not necessarily a binary operation because X' * C in general. Nevertheless, call a convolution simply because covers a wide range of "group convolutions' in today's GCNN literature.
Example 1. An orthodox Froup convolution is reproduced when T is the regular representation (of LCH group G) on X' L (G), i.c., 1 (h) = a(g h). In fact,
[ (hh)a(o-
[ =(h)a(h=')) g)dp(h)) = (x =a (g))
(x, 1a.Tylaa
(12)
where ā(g) 1(g- is involution.
Example 2. The cyclic convolution for an n-channel image x = (afj) ) R xm2xx is understood
as the when G Zon Zmgg X Rm xm2x and T (p.g)[a[(i,, [a] k)) -:-p.--- then
(x, TteTaalaaaa [al)Rmxxxpxx = Σ 2 iip-p p.j-9' i.
(13)
While the post-activation feature (a (g) b) is function on G, the input feature & can be an arbitrary abstract vector, which is general than typical GCNN formulations where feature is supposed to be a vector-valued function on G or G/H. This is an advantage for a more geometric understanding of CNNs, since the theory becomes free from the specification of x.
3.2 Continuous (G, T) Eqqivarria Vector-Valued Function f & C(G)
Definition 2. We say a vector-valued function f : CG is (G, -qqivvaanaa when
((Tg[=))(h) Lg[f(=)](h)) f(x)(g x X, g. E G.
(14)
Here, we restrict the definition for a special case of the regular representation L. This is simply due the fact that our GCNN satisfies this case.
Definition 3. Let G be a topological group. For any vector-valued function f f - CG put
[[fllcxxee)) [flci)--10) sup sup [f())
(15)
zeX geG
By Cegui( C(G)), we denote the normed vector space all continuous (G, eqquvvaraaa C(G)- valued functions X' equipped with the uniform norm ||.
[((();(())))
We note that the topology of uniform norm || lo(z)(()) is stronger than the topology of compact convergence, which is employed the cx-universality argument. fact, (x; C(G)) need not be complete (or Banach) to show the cc-universality.
5

---

3.3 Induced Lebesgue Measure À and Induced Fourier Transform ? on Subspace Xm
Let Xm denote an m-dimensional subspace of X, and let [es]ie[m] be orthonormal basis of Xm-
Induced Lebesgue Measure on Xm We induce the Lebesgue measure À on Am by pushing forward the Lebesgue measure dæ on I via an isometric linear embedding & R Xm For example, take a linear embedding 6(x) := Lielm] Iye;, Then, it preserves the length, and we can induce the Lebesgue measure on Xm as the push forward measure À = Φydæ so that the volume of hypercube = [Ze[m c:ē; G4 E [aa; b.]3 in Xm is caleulated x(Q) [astsm] |b; 1a--ad asl, and the integration of measurable function f Zm C over a measurable E Xm calculated as
J [ax)d{())
1
Σ Ieei
Σ
II
da
[ (E)
ʃo ((x)dx.
(16)
1=1
As far there is no risk of confusion, we denote da instead of dA(z).
Induced Fourier Transform on Xm. Using X, we induce the Fourier transform on R" as below: For any function Xm C,
fly) = S( Jx f(z)e (())e-kks d((z), f(x) = (2 Jx..
1 S Kly)e dd(y).
(17)
Here, the equality holds in at least three different senses (see the comments in 2.1
We remark (1) that once the subspace Xm is fixed, the induced Fourier transform is unique up to the orthogonal transformation of the basis (ei)s(m)) and (2) that the induced Fourier transform "on X" should not be confused with the Fourier transform "on group G Especially, this cannot map convolution x * o, an element in CG to a point product such as "Z ā".
3.4 Projection P: Xm and Extension Operator p*
In order to induce the Lebesgue measure X, we assume that the dimension of Xm to be finite. As a side effect this assumption, the image To [Tm] := (Tg [x]] g G. E Xm3 can extend toward the outside of X that is, Xm is not necessarily G-invariant (TalXm] c Xm). To avoid an "undefined error" such to input æ outside of Xm for a function f defined only on Xm. we introduce projection P and extension p* as below. When dim X' < 0o, we can omit P by putting Xm X' (so P = Id), because by the definition of the group representation, always TG[A] X.
Let X denote the orthogonal complement of Xm in X. projection onto X'm For any function f Xm - CG put
Let P X Xm denote the orthogonal
(18) This extends f (on subspace Xmm) to the entire space X' as a constant function on X that is, [=f(x + y) f(x + 0) for each a + y Xn, + X
(*)(=)(o) = f(P(=))(g),
Ze ze X G.
4 Main Results
We introduce the convolltinn neural networks and the corresponding ridgelet transform, and present the reconstruction formula for continuous GCNNs and the cc-universality for finite GCNNs.
Throughout this section, fix representation T' G GL(X') of group G (potentially (nfiniteddimensiona) Hilbert space X' over a field KK endowed with an inner product <-: and fix an m-dimensional closed subspace Xm, of X' equipped with an induced Lebesgue measure Let k = dimg K denote the real dimension of K, that is, k = 1 for K = R and l = 2 for K C. Let denote the identity element of G.
4.1 Integral Representation of (onnoliaool Neural Network
Definition 4. For any functions 7 : Xm x - and a : - C, we define the integral (atpreaaaattoo(Cc...ccooooootit convolltttn neural network as a vector-valued function X CG
representation of (G,
(1)()))g)) Jxm
7(a ()a((a)a(aa))) +r (g) b)dX(a)db, TE g G. (19)

---

Here, we call y parameter distribution, and a an activation function. If there is no risk of confusion, we abbreviate (a as da.
It is easy to that (G, ()- is (G, T) -eqiivaruu.. In fact, for every g, E G.
(T S X (T
b)dadb S[>](>)(g h).
(20)
In addition, at the identity element e, it is reduced to a FNN:
Sln]())(e)
2(1,))o((t,a)> (,, - b)dadb, DE X
(21)
Xm
and it satisfies projection property:
Shi(P[=)()) = (e)), X.
(22)
4.2 Ridgelet Transform and Scalar Product of Activation Function
Definition 5. For any functions f Xm CG and p: K C, we define the ridgelet transform
R[F;P((a,b) :- S (())())(((E)a)) a)x bjdx, (a, b) E Xm K.
(23)
Here denotes the identity element of G.
Definition 6. For any tempered distribution E S'KI)) and function e S(K), put scalar product
m- [ (w)
(o, = m=
- "dw.
(24)
Here, denotes the Fourier transform on K. which identified with the Fourier transform on E with & = dimg K. We note that ol is defined in the sense of tempered distributions.
The derivations of the ridgelet transform and the scalar product are clarified in the proof of the reconstruction formula. Some readers may notice that the ridgelet transform for GCNN is formally the same as the one for FNNs, and may wonder why inner product (x, a)x instead of group convolution (a #T (g). Indeed, this a consequence of two facts (1) that group convolution the identity is reduced to an inner product: (a # (e) (x, a)x, and (2) that when f is (G, -equuivariian,,, then the value (g) each g G is determined by translating the value f(x) (e) at the identity.
4.3 Reconstruction Formula, or the Universality of Continuous GCNNs
We state the first half of our main results. For f Xm CG we write fe(x) == f())(e) for short.
Theorem 1 (Main Theorem 1/2), Given a function Xm CG, assume (Al) that p*f X CG is (G, -equivraava,,,,,, i.e.,
p* (*T(T[()))))) = f(2)(g-(h), for every 2 X and g, h G;
(25)
and (A2) that I satisfies at least one of the following conditions: (A2a) both Se and Je are absolute- integrable, iee, Se E I. (X,,), (A2b) fa is square- integrabbte i.e., fe (2x),, or (A2c) fe is a tempered distribution, i.e., E S' (.())). Then, the following reconstruction formula holds:
S
*r x)) - b)dadb = ((a ((r.)))(a(())
(26)
J
where the equality holds at every continuous point v. of f for (A2a), in I.2 for (A2b), and in St for (A2c), respectively.
The proof is given in Appendix A.I.

---

4.4
co-Universality of Finite GCNNs
Finally, we state the second half of our main results. Let NN be the collection of finite GCNNs, that is,
NN U (z) Σ co((aa *T (g) b.) by, ci) Xm x K x C, [m]] REN
(27)
Since the reconstruction formula S(7;}] f with of R[ holds for arbitrary function f. we can construct sequence (Jn)nets of finite (G, -NCNNs that converges to an arbitrary target function f. namely
- f as n 00
(28)
by discretizing the continuous network S(7y] and distribution yy into finite sums
fa (z) = ((m))()(g)) - Σ Ca(((a *r x)))) - b,) with T' Σ (a
(29)
in a 'nice" manner so that 7n Y R[;;p] as n - oc. This is the primitive idea behind the constructive proof of the following co-universality of finite (G, (),CNN based on ridgelet analysis.
To state a regularity assumption on the activation function o, we introduce the forward difference operator A with difference 0 > 0, defined as
(t) :- a(t + 0) o(t), (+))= = A [t))(())
(30)
Theorem 2 (Main Theorem 2/2). For an activation function a E ('K)), assume (A3) that there exist E N and 0 > O such that Ag(o] is bounded and Lipschitz continuous. Then, NN is ce-universal;
that is, for any continuous (G, eeqquivari C(G)-valued function f Cequs(Ami C(G)), and
for any compact sets K Xm and L = G, there exists sequence (fn)nEN C NN finite GCNNs satisfying
If falle(K;CCLL)
ssup sup [f()((g) fr(()(g)) - -0 n
(31)
zek get.
The proof is given in Appendix A.2. Here, f Cequi C(G)) means that P*f is (G,T)- equivariant.
Examples
We display the ridgelet transforms and reconstruction formulas for few typical GCNNs. Besides, calculated in Examples and 8 the ridgelet transforms of a differential filter, which often reported to be acquired as feature map in the first layer of deep CNNs for image recognition 62 63
5.1 Finite Periodic Convolution Layer
Example (For I-dimensional periodic signals). The periodic convolution corresponds to the case when K = IR, G 2m a [m]] = {0, 1, ......,,. . 1}. X' = L²( = R equipped with the inner product (x, y) m Exe(me] Zyy/, and TT(=(() == ボyーı thus (a *T (1) m Eje(m] ayTs+j- Therefore, the ridgelet transform and the reconstruction formula are given by
R[fipl(a,b) mmm
f(z)(0)p (2 Exepm) - -b)
S[R(/:P](<>)))
R (la; b)g ( "Ejemgaaa:1 -b) dadb = (()))))())())
Jgm xR
Example 4 (For 2-dimensional multi-channer periodic images). 2-dimensional n-channel image is identified with a vector-valued function x z² IR",, thus X' = Rmmx xn, Let nk 4i denote the (i, j)th component in the k-th channel of x E X. Let G = z and put T T(p- [==g]=]ff == xp-p.iq- Therefore, the ridgelet transform and the reconstruction formula are given by
R[f: b) = Jam2n f(x) (
1 mmn Exe(m) Σ (m. [o of b) dx.
{[R[f:]](<))
R[f:A](a, b) m'n ExE(Mo on petiitssss - b) dadb (()))))(())))
gm
8

---

Example 5 (Difference operator (with cutoff function)). A difference operator on [m] is given by x Lxe(m]] 2 f(z) Eie(m] (1i+1 z;)d;, which is -equiveauvar
f(T](=)() = 1+] Tx = Ii+1-k Ii-k = f(z) - k). Since (())(0) = 21 - 20,
[ (z1 (01-20) -81-20010 (0=oo)1<(()p) Eielmaa, bb b)dx. Rm
R Ki pl (a,b)
We note since - 21 zo is integrable in IR we restrict f to compact set K R"" and impose the indicator function k as an auxiliary cutoff function.
5.2 (Deep Sets) Permutation Equivariant Maps on A Finite Set
Example 6. X R" G < S. and Tg[æ] (Ig (()- 10) (2-) (0 (g)) Thus (a, x)x
m Eyemm a, and (a #T ()) m Epsmm] a(0) So,
R[fipl(a,b) = Rmm f(z)(e)p 1 Eieema b)dx, dx,
{))))
R[f:p](a, b)o [pemmm] (pFal) - b) dadb = (o)p))((r(())
5.3 Continuous Periodic Convolution Layer
Example Let G T :- R/22Z {e f [- æ]] be the 1-dimensional torus group, which is one of the most basic continuous group. As consequence of the Fourier series expansion, (T)
is spanned by {eind E N). Hence, we can take X' to be an m-dimensional subspace X :=
[n|smm Fy e x-n In E IR) equipped with an inner product (ar, v)x : Sr (O)))(O)dd We note that the constraint ie, = x-n implies Σ In|-smm e = Σnn kmm Fn cos(n0) and thus any signal x E X is bandlimited real-valued continuous signal with each coefficient n, being the n-th frequency spectrum. Put Ta (x) == z(0 at), then (a (a) Sr a a(f)ar(a- 0)d0 Lnnlem on cncce En <m On cos(na) (by the convolution theorem and the constraint). Therefore,
R[f:pl(a.b) :=
f(x) Σ En On b)dz,
JRm
{1) JR
R[: p) b)o (Einkemene cos(no) -b)
b) dadb (aa, (())()
Example 8 (Differential operator (with convergence factor)). A differential operator d is calculated Enn <m en - f(x) Em e Since
f()) 2m n.n, is dg (()))) Eintee ne (ar)e Here, (de)eso = S(x) is family of convergence factors that satisfies (1) the first moment Sxx ( exists at every f, (2) Φt 1 in the weak sense as 1 - cc, and (3) (continuous and) (G, -uuuquivarra For example, we can take a Gaussian (.(x) = exp(- (=/(-1))3//4))) Hence,
not integrable on Rm,, we impose convergence factor d. as follows. [+(x) = (()) =
R[fup]((..))
Σ (x))) In -b) dx.
mmm
[n] =m
5.4 Euclidean group E(n) equivariant map
Example 9. The Euclidean group EE(n) is a semidirect product R2" x O(n) of the translational group Rn and the orthogonal group O(n), which acts on IR" as (U, s) t := Ut + for any R and (U,s) E ((n) R". So. put X' c (²RR)) and [x = xUU- (t - s)). Then,
R[f:pl(a. Jx f(x) O)p C a(t)x(t)dt - b bddr
((R[)>|](>((T.))> [
at (0)=)))(sssds - b) dadb (())(U,))

---

We note that more memory efficient representation for (RR) and/or a more general representation such (2()) and (E(3))), have been developed in the context of steerable CNNs [33 64
6
Discussion
6.1 Related Works on (G)CNN Universality
Non-Group CNN. Zhou 9 10 is the earliest show the ce-universality of deep ReLU (non-
group) CNNs. In 100. he presented (Theorem 1) the cc-universality in (; IR) in the limit of depth J co, and (Theorem 2) approximation error rate with respect to J. The CNN is carefully designed so that increasing depth also increases width, which is not covered in our GCNN.
Finite Group CNN. Maron al. [2]. Sannai et al. [65], Keriven and Peyré [66]. Ravanbakhsh 667 and Petersen and Voigtlaender 13 presented the co-(or -u-jverrersll results of finite-group CNNs. Maron et al. 112 is often cited one of the earliest publications, where the input space X R= xa (a-channel k-th order n-dimensional tensors), the output space is X" R= x (b-channel 1-th order n-dimensional tensors), the group G is subgroup of symmetric group Sn. and the group action (or representation) T is the fef-ttranslation (or left-regular representation). In this setup. they presented the co-universality of Ceep-Rel.UGGCNN, in the space of continuous G-equivariant functions Cegui (X; X'). The proofs are indirect because they are based on invariant polynomials MLPs. The finite group cases are essentially covered Example (Deep Sets).
Lie Group CNN. Yarotsky carefully designed deep GCNNs with Lie groups acting on infinite- dimensional input/output spaces, and show a version of universality in the space of continuous G-equivariant functions CL' R L2 Rc)). To be precise, G' is either compact group. translation group Rd or 2-dimensional roto- tro--rannlltion group SE(2), and the input/output spaces X' and X' are square-integrable functions on G. The proposed networks are not covered in our GCNNs, but several infinite group cases are covered in Examples 7
Remarkably, Kumagai and Sannai (14), Kumagai al. [15 introduced integral representation that covers LCH groups, and showed the universality. The proposed integral representation is based on the Haar measure, thus slightly different from ours. The proofs are indirect because the network is converted to an MLP.
6.2 Review of Assumptions
Group G. We only assume G to be topological group, to deal with continuous functions on G. Thus, a quite large class of groups are covered, for example, all the finite groups such as En, and Sn, compact groups such as SO(n) and U(n), and non-compact groups such as R and E(n) as well.
Representation Space X. Unlike previous studies, it does not need to be a function space such as C(G) and LG)GHH), but it only needs to be an abstract Hilbert space, which is one of the major advantages for geometric understanding of GCNNs. On the other hand, we introduce an auxiliary fiite-dimmnniionl subspace Xm (and projection P), to use the Fourier inversion formula on the finite-dimensional Euclidean space R. in the proof. We conjecture that the extension to an infiitt-dimeensionll setting would be a routine for some specialists in functional analysis.
Group Representation T. It does not need to be unitary, irreducible, nor square-interrable, since the proof is based only on a few basic properties of the linear group representation.
Network Architecture. The ridgelet theory supports wide class of activation functions, namely, the tempered distributions (S'). The extension to deep GCNNs remains an important open question.
Acknowledgments and Disclosure of Funding
The authors are grateful to anonymous reviewers for their valuable comments. This work was supported by JST CREST JPMJCR2015 and JPMJCR1913, JST PRESTO JPMJPR2125, and JST ACT-X JPMJAX2004.
10

---

References
[1] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličkovié. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges) arXiv preprint: 2104.13478, 2021.
[2] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2017.
[3] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep Sets In Advances Neural Information Processing Systems 30, 2017.
[4] Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 2747-2755, 2018.
[5] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks) In International Conference on Learning Representations, 2019.
[6] Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling, Spherical CNNS In International Conference on Learning Representations, 2018.
[7] Taco S Cohen, Mario Geiger, and Maurice Weiler. A General Theory of Equivariant CNNs on Homogeneous Spaces In Advances in Neural Information Processing Systems 32, 2019.
[8] Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-Giordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network] In Advances in Neural Information Processing Systems 37, 2018.
[9] Ding- Xuan Zhou. Deep distributed convolutional neural networks: Universality Applications, 16(06):895 2018.
Analysis and
[10] Ding- Xuan Zhou, Universality of deep convolutional neural networks Applied and Computa- tional Harmonic Analysis, 48(2)7887-794, 2020.
[11] Dmitry Yarotsky. Universal Approximations of Invariant Maps by Neural Networks Construc- tive Approximation, 55:407 474,004774444 2022.
[12] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks) In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 4363-4371, 2019.
[13] Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and fully-connected networks Proceedings of the American Mathematical Society, (4844):1577-5811 2020.
[14] Wataru Kumagai and Akiyoshi Sannai. Universal Approximation Theorem for Equivariant Maps by Group CNNs arXiv preprint: 2012.13882, 2020.
[15) Wataru Kumagai, Akiyoshi Sannai, and Makoto Kawano. Universal approximation with neural networks on function spaces Journal of Experimental & Theoretical Artificial Intelligence, pages 1-12, 2022.
[16] Sho Okumoto and Taiji Suzuki. Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness In International Conference on Learning Representations, 2022.
[17] George Cybenko. Approximation by superpositions of a sigmoidal function Mathematics of Control, Signals, and Systems (MCSS), 2(4):303-314, 1989.
[18] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators Neural Networks, 2(5):359-366, 1989.

---

[19] Bunpei Irie and Sei Miyake. Capabilities of layer-d perceptrons In IEEE International Conference on Neural Networks, pages 641 648, 1988.
[20] Ken-Ichi Funahashi, On the approximate realization of continuous mappings by neural networks Neural Networks, 2(3):183 192, 1989.
[21] S. M. Carroll and B. W. Dickinson. Construction of neural nets using the Radon transform In International Joint Conference on Neural Networks 1989, volume 1, pages 607-611. IEEE, 1989.
[22] Yoshifusa Ito. Representation of functions by superpositions of step or sigmoid function and
their applications to neural network theory Neural Networks, 4(3):385-34, 1991.
[23] H.N Mhaskar and Charles A Micchelli, Approximation by superposition of sigmoidal and radial basis functions, Advances in Applied Mathematics, 13(3)350-373, 1992.
[24] H. N. Mhaskar. Neural Networks for Optimal Approximation of Smooth and Analytic Functions Neural Computation, 1777 1996.
[25]
Andrew Barron. Universal approximation bounds for superpositions of a sigmoidal function IEEE Transactions on Information Theory, 39(3):930-945 945, 1993.
[26] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function Networks, 6(6):861-867, 1993.
Neural
[27] Noboru Murata, An integral representation of functions using three-layered betworks and their approximation bounds Neural Networks, 96):947-956, 1996.
(28)
Emmanuel Jean Candès. Ridgelets: theory and applications
PhD thesis, Standford University,
1998.
[29] Boris Rubin. The Calderón reproducing formula, windowed X-ray transforms, and Radon transforms in L S-sspacss Journal of Fourter Analysis and Applications, 4(2):175-197, 1998.
[30] Matus Telgarsky. Benefits of depth neural networks In 29th Annual Conference on Learning Theory, pages 1 1-23, 2016.
[31] Dmitry Yarotsky. EEroor bounds for approximations with deep ReLU networks) Neural Networks, 94:103-114, 2017.
[32] Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks Neural Networks, 108:296-333 -300, 2018.
[33] Taco Cohen and Max Welling. Steerable CNNs In International Conference on Learning Representations 2017, pages 1-14,
[34] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks In Advances in Neural Information Processing Systems 3I, pages 8571-8580. 2018.
[35] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wiid Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent In Advances in Neural Information Processing Systems 32, pages 8572-8583, 2019.
[36] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 322-332, 2019.
[37] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming In Advances Neural Information Processing Systems 32, pages 2937-2947, 2019.
12

---

[38] Jonathan Frankle and Michael Carbin. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks International Conference on Learning Representations, pages I 1-42, 2019.
[39] Atsushi Nitanda and Taiji Suzuki. Stochastic Particle Gradient Descent for Infinite Ensembles arXiv preprint: 1712.05438, 2017.
[40] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks Proceedings of the National Academy of Sciences, 113(33):
E7665-E7671, 2018.
[41] Grant Rotskoff and Eric Vanden Vanden-Eijnden. Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks In Advances in Neural Information Processing Systems 31, pages 7146-7155, 2018.
[42]
Lénaïc Chizat and Francis Bach. On the Global Convergence of Gradient Descent for Over parameterized Models using Optimal Transport In Advances in Neural Information Processing Systems 32, pages 3036-3046, 2018.
[43]
Justin Sirignano and Konstantinos Spiliopoulos. Mean Field Analysis of Neural Networks: A Law of Large Numbers SIAM Journal on Applied Mathematics, 80(2):225-752, 2020.
[44]
Taiji Suzuki. Generalization bound of globally optimal non-convex neural network training Transportation map estimation by infinite dimensional Langevin dynamics In Advances in Neural Information Processing Systems 33, pages 19224-19237, 2020.
[45] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda. Ghosts in Neural Networks: Existence Structure and Role of Infnite-Dimensione Null Space arXiv preprint: 2106.04770 2021.
[46] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda, Ridge Regression with Over-Parametrized Two-Layer Networks Converge to Ridgelet Spectrum In Proceedings The 24th International Conference on Artificial Intelligence and Statisties (AISTATS) 2021, volume 130, pages 2674- 2682, 2021.
[47] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Proceedings of the 32nd Conference on Learning Theury, volume 99, pages 2667-2690, 2019.
[48] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case In International Conference on Learning Representationss 2020.
[49] Rahul Parhi and Robert D Nowak. Banach Space Representer Theorems for Neural Networks and Ridge Splines Journal of Machine Learning Research, 22(43):1 2021.
[50] Michael Unser. A Representer Theorem for Deep Neural Networks Journal of Machine Learning Research, 100110) 2019.
[51] David L Donoho. |meergig applications of geometric multiscale anal analysis Proceedings of the ICM, Beijing 2002, 1:20-2233, 2002.
[52] Jean-Lue Starck, Fionn Murtagh, and Jalal M. Fadili. The ridgelet and curvelet transforms In Sparse Image and Signal Processing: Wavelets, Curvelets, Morphological Diversity, pages 39-118. Cambridge University Press, 2010.
[53] Gitta Kutyniok and Demetrio Labate. Shearlets: Multiscale Analysis for Multivariate Data Applied and Numerical Harmonic Analysis. Birkhäuser Boston, edition, 2012.
[54] Sho Sonoda and Noboru Murata, Neural network with unbounded activation functions is universal approximator Applied and Computational Harmonic Analysis, 43(2):233-22 2017.
[55] Kostadinova, S Pilipovié, Saneva, and J Vindas. The ridgelet transform of distributions Integral Transforms and Special Functions, (5(5))344-355 2014.
13

---

[56] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda. Fully- Colly-Conneeted Network on Noncompact Symmetric Space and Ridgelet Transtorm based on Helgason-Fouras Analysis, In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 20405-20422, 2022.
[57] Loukas Grafakos. Classical Fourier Analysis York, second edition, 2008.
Graduate Texts in Mathematics. Springer New
[58] I. M. Gel'fand and G. E. Shilov. Generalized Functions, Vol. 1: Properties and Operations. Academic Press, New York, 1964.
[59] Gerald B. Folland. A Course in Abstract Harmonic Analysis Chapman and Hall/CRC, New York, second edition, 2015.
[60] Bharath K. Sriperumbudur, Kenji Fukumizu, and Gert R. G. Lanckriet. Universality, Character istic Kernels and RKHS Embedding of Measures) Journal of Machine Learning Research, 12 (Jul):2389 2410, 2010.
[61] Allan Pinkus. Approximation theory of the MLP model in neural networks Acta Numerica, 143-195, 1999.
[62] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet Classification with Deep Convolutional Neural Networks In Advances in Neural Information Processing Systems 25, pages 1097-1105, 2012.
[63] Matthew D. Zeiler and Rob Fergus. Visualizing and Understanding Convolutional Networks In European Conference on Computer Vision, pages 818 18883, 2014.
[64] Maurice Weiler and Gabriele Cesa. General E(2)--qqivariant Steerable CNNs In Advances in Neural Information Processing Systems 32, 2019.
[65] Akiyoshi Sannai, Yuuki Takai, and Matthicu Cordonnier, Universal approximations permu-
tation invariant/equivariant functions by deep neural networks, arXiv preprint: 1903.01939, 2019.
[66] Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks In Advances in Neural Information Processing Systems 32, 2019.
[67] Siamak Ravanbakhsh. Universal Equivariant Multilayer Perceptrons Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7996 7996-8006, 2020.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "rVH7zyBX9U1", "reviewer": "Reviewer_8Jwn", "summary": "The authors prove the (cc-) universality property of group convolutional neural networks (GCNNs) with one hidden layer using the tools from ridglet theory.\nTo do so, the authors derive the first closed form solution for the ridglet transform of GCNNs, covering a wide spectrum of existing equivariant model designs.\n", "questions": "The authors claim that existing universality proofs for GCNNs are indirect and rely on the universality of either fully-connected networks or invariant polynomials, while the proposed method is direct and constructive.\nUnfortunately, I am not familiar with the literature on the universality property; could the authors elaborate further about the limitations of these existing methods and the benefit of the proposed one?\n\nIs this proof considered constructive because of the existence of the reconstruction formula for the ridglet transform?\n\nWhat kind of conclusions can be drawn from this theoretical work?\nDoes this proof provide any new intuition about GCNNs with respect to previous methods?\n\n\nLine 189: why is this an advantage for geometric understanding of CNNs? Could you elaborate further on this?\n", "limitations": "While the work seems rigorous, I think it misses some motivation and an analysis of the theoretical results.\nHowever, I am not familiar with the related literature on universality properties of neural networks.\n", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The manuscript is well written and the presentation is clear.\nThe contributions are clear and novel and the theoretical analysis seem rigorous (although I am not an expert on ridglet analysis and universality proofs).\n\nWhile the universality of GCNNs is a well known fact, existing proofs were only indirect or existential, while the proposed proof is constructive.\nHowever, I feel like the manuscript does not motivate sufficiently well why this difference is important; see \"Questions\".\n\nFinally, while the work seems quite rigorous, the authors do not comment much on their final result.\nIndeed, the paper is missing a proper \"conclusion\" section, stating what the main take-away points should be.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "R7vAcoiPImw", "reviewer": "Reviewer_onTd", "summary": "This paper uses the ridgelet theory technique to show the universality of group convolutional neural networks for various groups and feature spaces. Their results are new in the way that they apply ridgelet theory to group CNNs. Prior works have used ridgelet transform to show the universality of fully-connected neural networks, and literature exists on the universality of GCNN for limited groups. ", "questions": "Answering the following questions is to provide insight into the significance of the method and its novelty. Please explain\n\n1. How the method differs from others?\n2. How difficult and unique the analysis are compared to the one using ridgelet for fully-connected networks? Is it a trivial extension?\n3. How do their universality results for GCNN differ from already existing literature on GCNN? The authors have briefly touched on this, but it needs more clarification.\n", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The universality of GCNN is of interest to the community. The paper provides a proper amount of details and explanations. However, I found the paper a bit hard to follow. Many terms are defined without additional explanation/elaboration. For example, Section 5 provides several examples without any description. Moreover, I recommend covering related works in more depth.\n\nThe originality and significance of the work are unclear: 1) ridgelet transform as a technique is previously used for the universality of fully-connected networks, and 2) prior works have shown the universality of GCNN under certain conditions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LyanRyZkT6h", "reviewer": "Reviewer_VpiC", "summary": "This paper considered the approximation property of GCNNs on the frame of the ridgelet theory. By representing a typical GCNN into a nonlinear mapping between group representations, corresponding formulations on $(G,T)-convolution$ and $(G,T)-equivariance$ are established for the convenience of further demonstration under ridgelet-frame. The main results showed the cc-universality of GCNNs in a constructive and unified manner. ", "questions": "Is graph equivariant NNs (such as SE(3)-transformer) an example of ridgelet transform-based CNNs?", "limitations": "This is theoretical study. There is no negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths: The ridgelet transform induced group convolution can cover typical class of neural network convolutions such as deep sets and E(n)-equivariant convolutions. This study derives the ridgelet transform for a general class of GCNNs. The reconstructed formula is given which discretized version is then applied to prove the universality of (G,T)-CNNs. The cc-universality of GCNNs for a general class of group equivalent continuous vector-valued functions is shown as an example. Examples of GCNNs are given.\n*Weaknesses: It is best the numerical experiments are shown to test the theory developed.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IAyyFSUehuU", "reviewer": "Reviewer_sVAk", "summary": "[updated score from 6->7 based on technical soundness and contribution to DL theory]\n\nThe paper describes a mathematical analysis of group convolutional neural networks, showing that they are universal approximators. To show this, the authors derived the ridgelet transform (a mathematical analysis tool) for G-CNNs. This is a result in itself, which is further used in this paper to provide a constructive proof of universality.", "questions": "Important:\n1. Why is it important to derive the ridgelet transform? \n2. How should I interpret this transform? \n3. Why can we show universality once it is derived?\n\nLess important:\n\n4. Line 87: \"As an application, we show ...\" Are there any other applications of the ridgelet transform? I find it hard to assess the impact of the result of deriving it.\n\n5. Line 184: Fourier transform on $\\mathcal{H}$, this is way more abstract then I have ever seen the FT (most general to me is FT based on group irreps). Is it possible to give interpretation to this? Why do we still call it a Fourier transform?", "limitations": "I see no issues here.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n* The paper is technically sound and rigorous\n* The proposed proof constructive and does not rely on indirect proofing methods\n\n**Weaknesses**\n* The paper is very technical, and could perhaps better fit a mathematical functional analysis venue, rather than an ML conference. The theme (universality of G-CNNs) falls within the conference scope, but the content otherwise is purely mathematical\n* Related is my concern about the impact of the paper in the field. What is the relevance of a new universality proof? I see the beauty/elegance of the paper, but that is on math merits, not on ML principles per se.\n* The paper could overall benefit from a more intuitive exposition. Why is it important to derive the ridgelet transform? How should I interpret this transform? Why can we show universality once it is derived?\n\nI believe the paper could be a great contribution to NeurIPs if it were to be made more accessible to a broader audience (like me, I like to learn from these papers, but this one was actually far out my comfort zone). E.g. up and until page 3.2 I could clearly follow everything, but what comes after I had to read several times to understand, and still don't fully understand the significance of e.g., 3.3. These are things a mathematician may get straight away though..\n\n**Minor details**\n\nline 54: Could you provide some intuition on the role of $\\gamma$ in equation 2. It somehow weights the different parameter sets (kernel a, bias b) and can be used to rewrite into (1), but a bit more intuition may be helpful.\n\nline 64: What does $C(G)$ denote? Only later are such spaces defined, but not yet this early..\n\nLine 69: I like the analysis - synthesis viewpoint of R and S, in relation to the Fourier transform. This was helpful.\n\nLine 87: \"As an application, we show ...\" Are there any other applications of the ridgelet transform? I find it hard to assess the impact of the result of deriving it.\n\nLine 126: Why do you refer to it as a *generalized* form of the group convolution? I have seen this form several times with $\\mathcal{H}=\\mathbb{L}_2(G/H)$. Does generalized refer to the fact that $\\mathcal{H}$ can be different then the usual function spaces?\n\nLine 151: This sentence misses a part!\n\nLine 158: Why does f now map to $\\mathbb{C}^G$ and not $C(G)$?\n\nLine 184: Fourier transform on $\\mathcal{H}$, this is way more abstract then I have ever seen the FT (most general to me is FT based on group irreps). Is it possible to give interpretation to this? Why do we still call it a Fourier transform?\n\nLine 221: What does notation $f(\\cdot,e)$ mean? Is it the same as $f(\\cdot)(e)$?\n\nLine 263: This is another example of where I understand the explicit forms (of the ridgelet trafo and reconstruction formula), however, I do not understand why it is relevant for me to read this. One the one hand it is nice to see explicit examples, on the other hand side I do not understand what to do with it? E.g., what are the implications to the universality proof?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept