Unified Universality Theorem for Deep and Shallow Joint-Group-Equivariant Machines

We thank the reviewer for their high score and positive comments about our paper.

Comments on Weaknesses

• … they do not show that the approximation error can be reduced by increasing width (or at what rate this error reduces).

We agree that the approximation rate is an important step to further conduct generalization error analysis. In general, there have already been known several approaches to obtain an approximation rate (such as Barron’s rate and Jackson’s rate), and the focus of this paper may diverge, it would be a subject for future work.

Answers to Questions

• … I am fairly confident in the main theorem, but I found it a bit hard to see when exactly the conditions are satisfied. Seeing more examples of concrete networks where the conditions are satisfied, and importantly, examples where they fail, would help me better appreciate the theorem and convince myself of its significance.

As also commented to Reviewer Vqs4, further investigations on the sufficient condition for Theorem 4 are important directions of research in deep learning theory. As presented in Lemmas 1-3, constructing joint-equivariant maps is much easier than constructing classical (non-joint) equivariant maps. In fact, in fully-connected networks (Sec.5) and quadratic-form networks (Sec.6), the joint-equivariance holds for any activation function. It is rather difficult to state the condition when joint-equivariance cannot hold. We note that joint-equivariance does not immediately imply universality, that is, the constant $((\phi,\psi))$ in Theorem 4 could degenerate to zero or diverge depending on feature maps. For the case of depth-2 fully-connected networks, it is known that the constant is zero if and only if the activation function is a polynomial function. In general, such a condition can be investigated in a case-by-case manner. Fortunately, we can use the closed-form expression of the ridgelet transform to our advantage. (We have supplemented this in Remark 3-3)

Reviewer oWLq pointed out that there is significant overlap with an earlier paper. I have looked at it and I agree that the overlap is non-trivial, although I still consider the present paper novel enough (as argued also in the author rebuttal). I will update my score to 6.

We thank the reviewer for their thoughtful comments and questions.

Comments on Weaknesses

• Significant overlap with previous work [1].

The mere similarity in formal appearance does not necessarily imply similarity in meaning or content. For example, while the Eulerian path problem can be solved efficiently, the Hamiltonian path problem, which appears quite similar, is NP-complete. Similarly, while a linear combination of affine functions remains affine, a linear combination of affine functions followed by tanh, namely a neural network, can approximate any continuous function.

This study is different from [1] in the class of learning machines. The previous work cannot deal with deep structures or composite maps and, therefore, falls short as a theoretical analysis of deep learning. This limitation arises because joint-invariance alone is insufficient to construct irreducible representations for deep structures.

More technically, it is due to the facts (1) that an inner tensor product $\pi_1 \otimes_i \pi_2$ of irreps $\pi_1, \pi_2$ is not always irreducible, while (2, or Lemma 4) that an outer tensor product $\pi_1 \otimes \pi_2$ or irreps $\pi_1, \pi_2$ is always irreducible. The two facts (1) and (2) appear similar (thus confusing) but the essential consequences are different. Further, (3) that deep feature maps are often vector-valued, but (4) that the previous study is limited to scalar-valued joint-invariant feature maps. In the previous study, due to (1) and (4), it is technically hard to obtain an irrep for vector-valued feature maps. Namely, just a $d$-times inner tensor product $\pi_s \otimes_i \cdots \otimes_i \pi_s$ of irrep $\pi_s$ acting on scalar-valued joint-invariant maps $\phi_s$ cannot be an irrep acting on $d$-dim. vector-valued feature map $\phi_s \otimes \cdots \otimes \phi_s$. On the other hand, this is based on not (1) but (2), we have successfully constructed an irrep as presented in Section 5 (Depth-n Fully-Connected Network). Furthermore, as demonstrated in Lemmas 1–3, the joint-equivariance enables a natural handling of (not only fully-connected but any) deep structures. By seemingly making a small adjustment to the conditions, we were able to address a fundamental problem effectively. (We have supplemented this in Remark 4)

• Lack of examples covering models commonly used in the equivariant ML literature.

As mentioned in Remark 1, all the equivariant feature maps are automatically joint-equivariant. Hence by assuming the irreducibility of an appropriate unitary representation $\pi$ of $G$ on $L^2(X;Y)$, we can conclude the universality from our main theorem. In fact, however, the universality of group-equivariant networks have already been shown in a unified manner by using the ridgelet transform in Sonoda et al. (2022a). The feature map is defined in Eq.19 as $\phi( x, (a,b) )(h) = \sigma( (a *_T x)(h) - b )$, it is indeed joint-equivariant because $\phi( g.x, g.(a,b) )(h) = \sigma( \langle(h^{-1}g).x, a\rangle- b ) = \phi( x, (a,b) )(g^{-1}h)$ with $G$-action on parameters $(a,b)$ being trivial, and as showcased in Section 5, this feature map covers a wide range of typical group-equivariant networks such as Deep Sets and $E(n)$-equivariant maps. We have supplemented this fact in the revised manuscript. (We have supplemented this in Section 7)

• Numerous technical lemmas hinder readability and obscure the main message.

Those Lemmas are stated as concrete examples of joint-equivariant maps. We have moved some proofs to Appendix, and supplemented more comments and remarks.

Answers to Questions

• Can the authors clarify the differences between the presented paper and [1] and explain how this work provides novel insights relative to the cited paper?

Please refer to Comments on Weaknesses.

• Could the authors elaborate on the relevance of the examples presented in Sections 5 and 6 within the context of current equivariant ML literature?

As mentioned in the abstract, these are not equivariant networks. Joint-equivariance is not a restriction but an extension of classical non-joint equivariance. Thus our main theorem covers classical equivariant networks. Please also refer to Comments on Weaknesses.

Summary of the discussion

The discussion has revolved around the similarities and differences between our work and previous study [1], particularly concerning the main theorem. Below is a summary of the key points raised:

Factual Points:

• Limitations of [1]: Previous Study [1] is limited in its ability to handle depth-$n$ models, a shortcoming that our study explicitly addresses and resolves.
• Contributions of this study beyond the main theorem:
  • The introduction of the novel concept of joint-equivariance.
  • New theoretical results, including Lemmas 1–3.
  • Explicit definition of constructive solution operators for general depth-$n$ networks (not restricted to fully connected networks), as presented in Corollary 1.
  • Concrete examples of irreducible representations for depth-$n$ fully connected networks.

Reviewer’s Opinion:

• Reviewer oWLq appears to place significant emphasis on the similarity in the formal structure of the main theorem between our work and [1], which may contribute to an underestimation of the differences in their substantive contributions.
• The reviewer acknowledges the general principle that similarity in formal appearance does not necessarily imply similarity in meaning or content. Despite this, they express concerns about the perceived "research effort" and use the visual similarity in the proof of the main theorem to question the overall value of the study.

Authors’ Response:

• While the proof of the main theorem may appear similar to that of [1], the broader contributions of this study are distinct and substantial. Focusing solely on a single aspect (such as the similarity in a part of the proof) risks undervaluing the overall contributions of this research.
• The issue of "research effort" is subjective and difficult to measure objectively. Using it as a basis for rejection leaves limited room for constructive dialogue.

Open Question:

• The authors have asked the reviewer a specific question that remains unanswered:

  If the reviewer were to use our main theorem in their future work, would they simply cite [1] and repeatedly fill in the gaps themselves to account for the differences?

Reviewer Vqs4 does not ask

what happens in the case where $G$ acts trivially on the parameter domain

If you do not want to use any non-trivial group action on the parameters, nonlinearities can easily break the equivariance, so you have to carefully handcraft the network architecture so that the network is group equivariant. On the other hand, if you use non-trivial group action, you can much easily find a $G$-action on parameters, as demonstrated in Sections 5 and 6. For example, you can try finding a further extension of the case of quadratic-form to $\sigma \circ \mathrm{polynomial}$.

We have sincerely addressed all three points of feedback; however, it seems as though this has had no impact on the scores. Is this truly reflective of a fair and constructive discussion?

I have to say that I do not appreciate the tone of the authors' response to the remarks made by reviewer oWLq. This should be a constructive discussion and the authors should rather be thankful to the reviewers whose reviews have the overall goal of improving this manuscript. Wordings such as "overly fixated" do not contribute to a constructive discussion.

Due to the limited constructiveness of the discussion so far, I am considering lowering my score.

We thank the reviewer for their positive score and productive questions.

Comments on Weaknesses

• First it appears to be a limitation of the work, that the presented theory only applies to joint group equivariant networks... In Remark 1, also Figure 1, it is however stated that the group-equivariant networks are included as a subclass of joint equivariant networks, as those for which G acts trivially on the parameter domain.

Certainly, joint-G-equivariance is not a restriction but an extension of the classical notion of G-equivariance, and in fact, all G-equivariant feature maps are joint-G-equivariant. (We have emphasized this in Remark 1.)

• This raises some concerns, if all of the developed theory applies to this case. Theorem 4, which is the core of the established theory and defines the ridgelet transform, relies on irreducible representations of the group actions, both for the input as for the parameter space. If however we would require the irreducible trivial representation for the parameter space but not for the input space then the question arises if all of the proofs still hold for this case. This might trivially be the case but because of its importance a comment on this special case would strengthen the manuscript.

If we understand your concerns correctly, there seems to be a misrecognition in

irreducible representations of the group actions, both for the input as for the parameter space.

In fact, the irreducibility is assumed only for $\pi$, the representation on the functions $f:X \to Y$ on data domain, but not for $\hat{\pi}$, the representation on the distribution $\gamma : \Xi \to \mathbb{R}$ on parameters. This asymmetry originates from the fact that our main theorem only focuses on (the universality of) $LM[\gamma;\phi]:X \to Y$, not on its dual $R[f;\psi]:\Xi \to \mathbb{R}$. However, when the dual $\hat{\pi}$ is irreducible, then we can state $R \circ LM[\gamma] = \gamma$ for any $\gamma \in L^2(\Xi)$ (the order of composition is reverted from $LM \circ R[f] = f$). (We have supplemented this in Remark 3-2.)

• Further information on the underlying assumptions for the non-linearities is needed. For group equivariant networks it is well-known that arbitrary non-linearities might destroy group-equivariance. It would be important to state which assumptions need to hold for the non-linearities for the joint group equivariant case and group equivariant case (in which G acts trivially on the parameter domain).

We agree that this is an important direction of research in deep learning theory. Both necessary and sufficient conditions on activation functions for universality remain open problems. As you suggested, nonlinearity can easily break the classical (i.e. non-joint) equivariance. On the other hand, joint-equivariance is more likely to hold. In fact, in fully-connected networks (Sec.5) and quadratic-form networks (Sec.6), the joint-equivariance holds for any activation function. We note that joint-equivariance does not immediately imply universality, that is, the constant $((\phi,\psi))$ in Theorem 4 could degenerate to zero or diverge depending on the feature maps. For the case of depth-2 fully-connected networks, it is known that the constant is zero if and only if the activation function is a polynomial function. To this date, however, such a condition is shown in a case-by-case manner, and the general principle is not known. In general, such a condition can be investigated in a case-by-case manner. Fortunately, we can use the closed-form expression of the ridgelet transform to our advantage. (We have supplemented this in Remark 3-3.)

Answers to Questions

Please refer to Comments on Weaknesses.

Regarding irreducible representations:

I thank the authors for their comments. I would suggest that a discussion of above points is being added to the paper as well as I believe that the "misrecognition" regarding irreducible representations could be prevented by adding an explicit discussion of this fact to the main body of the paper.

Regarding G-equivariance:

Further, I suggest that there should be a dedicated paragraph in the paper which lays out the theory for the special case of (non-joint) G-equivariant networks, as this is one of the main generalizations of this work with respect to previous work.

Further comments with respect to nonlinearities are needed in this context. It is not clear under which assumptions the developed theory still holds for the (non-joint) G-equivariant case in the presence of nonlinearities and the necessary assumptions need to be clearly stated. Remark 1 states that G-equivariance is a special case of joint-G-equivariance; this however seems to contradict the following statement of the authors in this rebuttal: "nonlinearity can easily break the classical (i.e. non-joint) equivariance. On the other hand, joint-equivariance is more likely to hold." If the theory holds for joint-G-equivariance I would assume that it also should hold for the special case of G-equivariance without restriction. Also the statement that joint-equivariance is "more likely to hold" is not well defined. I encourage the authors to discuss this aspect more clearly.

In its current form, the manuscript does not develop above points sufficiently and the discussion in the rebuttal has not yet completely answered my concerns. A dedicated paragraph that discusses the extent to which the developed theory holds for G-equivariant networks is needed for clarification and would greatly improve the manuscript.

I appreciate that the authors added section 7 with an example for a G-equivariant network. This section however does not explain how the current framework of this paper could be applied to G-equivariance, but instead refers to the previously existing framework in Sonoda et al. (2022a). This does not shed light on the applicability of the method presented here.

Further, there seem to be some references in section 7 to equations and sections in Sonoda et al. (2022a), which need to be made more specific:

"The feature map is defined in Eq.19 as"

"As showcased in Section 5, ..."

I assume these refer to Eq. 19 in Sonoda et al. (2022a), and section 5 in Sonoda et al. (2022a). However this is just an assumption and should be explicitely stated in the text.

Applicability to G-equivariant networks of the theory developed in this paper, in conjunction with the exact assumptions that need to be fulfilled, would be a major contribution of this work, that should not only be mentioned in Remark 1, and reduced to a reference to Sonoda et al. (2022a), but instead clearly worked out in further detail here.

According to the suggestions from Reviewer Vqs4, we have major updated "Section 7: Example for Classical Equivariant Network", and presented additional novel result: the ridgelet transform for depth-$n$ group convolutional networks (GCNs). While depth-$n$ fully-connected network (FCN) is the most typical example of joint-equivariant (but not equivariant) learning machine, depth-$n$ GCN is the most typical example of equivariant (and thus joint-equivariant) learning machine. The paper is now well balanced with these two key examples. Because the section gets longer, we have moved it (from Section 7) to

• Appendix B: Example: Depth-$n$ Group Convolutional Network