Constructive Universal Approximation Theorems for Deep Joint-Equivariant Networks by Schur's Lemma

We appreciate your taking the time and detailed comments and suggestions.

• Q1. ...How feasible is it to implement these theoretical constructs in practical neural network architectures? Have the authors considered the computational complexity and resource requirements for applying these methods to real-world datasets, and if so, what strategies or approximations can be employed to make this approach computationally efficient?

Since the ridgelet transform is given by an integral expression, it is expected that sampling from the ridgelet transform by numerical integration could replace the standard learning method by loss minimization. Actually, the idea of discretizing the integral representation has a long history and can be traced back to Barron's integral representation [B]. In theory, it is known that we can show a faster discretization rate, called the Barron rate, by theoretically conducting numerical integration with convex optimization (or equivalently, kernel quadrature or quasi-Monte Carlo methods). In practice, achieving Barron's rate is not straightforward as it reduce to another loss minimization problem. However, in recent years, Yamasaki et al. [Y] developed an exponentially-efficient quantum algorithm to sample from the ridgelet transform. So the integral representation may be advantageous when the quantum computers become practical.

[B] Barron, Universal approximation bounds for superpositions of a sigmoidal function, IEEE Transactions on Information Theory, 39(3):930-945, 1993.

[Y] Yamasaki et al. Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation, ICML 2023

• Q2. The main results rely on several key assumptions, such as the local compactness of the group ( G ) and the irreducibility of the unitary representation ( \pi ). How robust are the findings to deviations from these assumptions? Specifically, can the authors provide more insights or alternative approaches for cases where these assumptions might not hold, such as in networks involving infinite-dimensional groups or non-compact groups?

First of all, locally compact group (LCG) is a sufficiently large class. As mentioned in ll.101-102, for example, it includes any finite group, discrete group, compact group, and finite-dimensional Lie group, while it excludes infinite-dimensional Lie groups. In particular, since finite-dim Lie groups include some non-compact groups such as $GL(n)$ and $R^n$, LCG includes those non-compact groups. Additionally, LCG may be sufficiently large to act on typical input and parameter spaces. For example, finite-dim manifolds (including finite-dim vector spaces) can be realized as homogeneous spaces of finite-dim Lie groups, so LCG may be adequate. Further, as also discussed in Limitation, whether it is really necessary to consider infinite-dimensional groups should be carefully considered.

Similarly, the motivation for the unbounded case is less clear. (Just to be sure, that a linear operator is "bounded" means it is "not Lipschitz continuous", and does not mean it is "literally bounded".) Since the integration operator $DNN \circ R$ is expected to be an identity map, it usually possesses much a stronger structure than just a boundedness.

However, if necessary, we will outline the basic policy of relaxing those assumptions (in the hope that motivated readers will become future collaborators). First, the assumption of LCG is required for taking an invariant measure. So, in cases of larger groups where an invariant measure cannot be taken, introducing convergence factor (an auxiliary weight function such as Gaussian) is the basic measure. Next, when the integration $DNN \circ R$ diverges, simply restricting the range of $R$ can settle the problem. This technique is adopted in Sonoda et al. [29] to show the $L^2$-boundedness.

• W1. While the paper is strong in its theoretical contributions, it lacks empirical validation through experiments or simulations...

We agree that numerical simulations are convincing. For example, we may try numerical integration of the reconstruction formula for DNNs shown in Section 4.2. However, due to the limitation of time we spent much effort on theoretical refinement. So we'd like to postpone this to important future work.

• W2. This work makes several assumptions, such as the local compactness of the group ( G ) and the boundedness of the composite operator ( \text{NN} \circ R )...

Please refer to response to Q2.

• W3. Some of the technical details, particularly those related to advanced concepts in group representation theory and the ridgelet transform, might be challenging for readers who are not experts in these areas. Providing additional intuitive explanations, diagrams, or examples to illustrate these concepts could enhance the clarity of the paper.

We appreciate your suggestions. We will add introductory explanations on group representation theory and ridgelet transform theory to the supplementary materials.

I thank the authors for responding to my comments. I want to keep my rating (borderline accept) since the method lacks empirical validation and is built upon various strong/weak assumptions.

We appreciate your comment.

the method lacks empirical validation and is built upon various is built upon various strong/weak assumptions.

We would like to clarify again that our assumptions are not so strong because

• joint-equivariance is much a general class than equivariance,
• locally compact group (LCG) is a sufficiently large class, and
• the boundedness of operator $DNN \circ R$ can easily hold (note again that it is not literally bounded but just Lipschitz continuous)

So, for example, our theorem covers both shallow and deep fully-connected network (which is not group equivariant but joint-group-equivariant) as presented in the example section In addition, our result trivially covers traditional group equivariant networks such as group-equivariant convolution networks.

So, please let us know which specific assumptions you think are stronger.

We appreciate your taking the time and detailed comments and suggestions. We are grateful for crediting the strict improvement from the previous study.

Let us point out and correct some major misunderstandings.

• Summary: This work generalizes the ridgelet transform to equivariant neural networks

This may cause the reviewer misevaluation. Our objective is not "equivariant" networks but "joint-equivariant" networks, which encompasses both equivariant and non-equivariant maps. For example, we deal with fully-connected networks, which is not equivariant in the ordinary sense. We present a unified criteria to verify the universality of deep/shallow equivariant/non-equivariant networks, which is the irreducibility of induced representation $\pi$.

• Significance/novelty: ... For example, many universality results already exist in equivariance (see e.g. work by Yarotsky [3], by Dym et al [2], etc.)

Our main result is much more general than previous studies in the universality of NNs. Typical previous studies such as Yarotsky [3] and Dym [2] are limited to specific groups $G$ (eg. compact gp, roto-translation gp $SE(n)$, symmetric gp $\mathfrak{S}_n$) acting on the Euclidean space $X=\mathbb{R}^d$, and carefully hand-crafted network architectures, while our results cover any locally compact group $G$ acting on any data domain $X$ (eg. function space, discrete sets), and any joint-equivariant feature map.

• Mathematical rigor: ... “Recall that a tensor product of irreducible representations is irreducible.” This is incorrect

This is incorrect. First, (a) an external tensor product representation of irreducible representations is irreducible (see e.g., Folland [10, Theorem 7.12]). On the other hand, (b) an internal tensor product of irreducible representations is not necessarily irreducible. It seems that the reviewer is confusing (a) with (b). In other words, the tensor product $\pi_1 \otimes \pi_2$ of the irreducible representations $\pi_1, \pi_2$ of groups $G_1$ and $G_2$, respectively, is an irreducible representation of the product group $G_1 \times G_2$ by (a), whereas it is not necessarily an irreducible representation of the component groups $G_1$ or $G_2$ by (b). In the case of Lemma 5, $\pi_1$ is irrep of $G_1 = O(m)$ on $R^m$, $\pi_2$ is irrep of $G_2 = Aff(m)$ on $L^2(R^m)$, and the representation $\pi$ in question is the tensor product $\pi_1 \otimes \pi_2$ of $G_1 \times G_2$. So, it is irreducible by (a).

• (contd) ... the authors discuss the assumption that the group is locally compact, but say that this “excludes infinite-dimensional groups”. Yet, this is also false...These errors are surprising.

This is incorrect. SO(3) is an infinite group (i.e., the cardinality of SO(3) as a set is infinite), but it is not an infinite-dimensional group but a finite-dimensional Lie group, and thus, it naturally falls under the category of locally compact groups.

• Also, the mathematical techniques themselves do not appear to be novel (for instance, Schur’s lemma is quite standard, and the proofs included in the main body are rather simple — Lemmas 1 and 2 are in fact widely known)...

We do not agree this. Lemmas 1 and 2 are key properties of joint-equivariant maps, which cannot be "well-known". We skimmed 50+ universality papers, but no paper used Schur's lemma to show the universality. Let us know if such a paper exist.

Q1. Yes. Please refer to A.1 in the supplementary pdf. We present a new network for which the universality was not known.

Q2. Neither of mathematical concerns raised are incorrect.

Q3. Please refer to A.2 in the supplementary pdf. We present a clarification of depth-separation with a cyclic group.

Q4. Because the semi-direct product is a sufficient condition for the equality $|G \ltimes H| = |G||H|$ holds, which maximize the effect of depth-separation.

Misc.

• Clarity:...

We appreciate productive feedbacks. We add backgrounds on the ridgelet transform and literature overview on the universality NNs.

• (contd) motivation for why one should value constructive approximation theorems for equivariant networks...

In the introduction, the motivation for focusing on constructive approximation via ridgelet transform is because it can explain how the parameters of the neural network are distributed. The reason why the scalar value is insufficient is explained in the paragraph on line 43. As for the FDN, it is explained in Sec. 5, so there is no need to refer to the previous study.

• (contd) what the practical use or theoretical value of the ridgelet transform is

Since the ridgelet transform is given in closed form, finite neural networks can be obtained by discretizing it. This is not possible with non-constructive proofs. Even with constructive proofs, a carefully handcrafted network is common, which is only a particular solution to the equation $DNN[\gamma] = f$. Although not demonstrated in this study, classical ridgelet transforms can describe the general solution [29]. Therefore, any solution obtained through deep learning can be described by the ridgelet transform.

We appreciate your taking the time and detailed comments and suggestions.

• Q1. The authors allude to cc-universality in the Limitations section, can you briefly explain the term and is it the same as defined in Micchelli et al., 2006 etc

Yes, it is the same. We supplement with a brief explanation in the revised version. Below is a vector-valued version.

Definition. Let $X$ be a set, $Y$ be a Banach space, and let $F$ denote a collection of $Y$-valued functions on $X$. We say $F$ is cc-universal when the following condition holds: For any compact subset $K$ of entire domain $X$, any function $f$ in $F$, and any positive number $\epsilon$, there exists a $Y$-valued continuous function $g$ on $K$ such that $\sup_{x \in K} \\| f(x) - g(x) \\|_Y \le \epsilon$.

It seems that the term cc-universal was introduced in the context of kernel methods in the 2010s to distinguish it from other topologies such as $c_0$-universal and $L^p$-universal. See, eg.,

• Sriperumbudur et al. On the relation between universality, characteristic kernels and RKHS embedding of measures, AISTATS2010.

In the standard mathematical terminology, it is called density in compact-open topology (the topology associated with compact convergence). In the 1980s, NN researchers (such as Cybenko and Hornik et al.) called it the universal approximation property, but this terminology is ambiguous in the choice of topology, so we call it cc-universal.

• Q2/W1. The biggest weakness of the work seems to be that it shares a vast amount of technical analysis, machinery and the fundamental proofs are shared with the earlier work by Sonoda et al. While the extension to a larger class of networks and the introduced vector values feature maps is certainly valuable, I am not fully convinced of the differential novelty of the work. Most of the (valuable) effort has been spent in a mostly natural extension of the previous work on the topic.

At the state of the previous study, it was not possible to include deep fully-connected networks, and this study resolved this issue. It is mainly because the previous study assumes scalar-valued maps. To deal with deep networks, scalar-valued is insufficient not only because typical hidden layer maps are vector-valued, but also because just taking a tensor-product of joint-invariant scalar-valued maps (which is vector-valued but) in general cannot represent a joint-equivariant vector-valued map. Without joint-equivariance, we cannot fully investigate the effect of group action on hidden layers (such as $NN_2$ in $NN_3 \circ NN_2 \circ NN_1$). So, we need to rebuild the framework from scratch.

Technically, we replaced the scalar-valued joint-invariant maps with joint-equivariant maps between any $G$-sets (Definition 3 is much more general than vector-valued maps). As described after Definition 3, this replacement resolves several technical issues. In particular, it could naturally deal with function composition (Lemma 2). As a result, we succeeded to deal with deep networks.

Additionally, another technical difficulty occurs in applying the main theorem, that is, to find an irreducible representation. In the end, of course, we have discovered the one (Lemma 5).

Note also there are many formulations we tried but did not work out before we arrived at this proof. Therefore, please be aware that what seems to be an obvious generalization is a kind of so-called Columbus' egg illusion.

• W2. The authors mention that assumption (5) (that the network is given by the integral representation) in limitations is potentially an "advantage". If that is so, a discretized version would be the preferred model since it is also closer to real world NNs

We agree your suggestion, and tried to write down the $cc$-universality of finite DNNs during the rebuttal period. However, the proof gets more than 3 pages. So we'd like to postpone to our important future work. The proof essentially repeats a parallel argument with Appendix A.2 in [30] twice: One is for discretizing single hidden layer (eq.24), the other is for discretizing entire network (eq.25). Both convergence are justified by the dominated convergence theorem for the Bochner integral.