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

How are your depth-n G-convolutional layers related to the group convolutional layers by Cohen et al?

Thank you for your question regarding concrete examples. We fully acknowledge the pioneering contributions of Cohen and colleagues in the development of group-equivariant neural networks.

The focus of this study lies in universality and a general geometric perspective. Therefore, in this paper, we chose to highlight a single representative example with a particular emphasis on differential geometric aspects, specifically the 2019 paper.

The relationship between the ridgelet transform of group-convolution networks and existing works—especially in the context of universal approximation theorems—is thoroughly discussed in Sections 5 and 6 of Sonoda et al. (2022a). We kindly refer the reviewer and future readers to these sections for further details.

The three papers suggested by the reviewer do not explicitly analyze the universality or expressive power of the proposed networks. The group convolutions in Group Equivariant Convolutional Networks and Steerable CNNs correspond to group convolutions where a finite group $G$ acts on $X = \mathbb{R}^{n \times n \times k}$ for some $n$ and $k$, and thus their universality follows as a corollary of Theorem 6.1. Similarly, the convolution in Spherical CNNs corresponds to the case where compact group $G = SO(3)$ acts on $X = \mathrm{SO}(3)$ (or homogeneous space $S^2$), and thus the universality can also be shown in the sense of Theorem 6.1.

The authors mention several times that this result unifies the universal approximation theorem. But it is not clear how Theorem 3.10 can imply the universal approximation theorem, say the one established by (Pinkus, 1999).

There is no unique definition of "universality." In the context of machine learning, the term "universality" typically corresponds to what is referred to as "density" in standard mathematical terminology. Accordingly, there exist various types of universality depending on the choice of topology.

For example, the notion treated in Pinkus (1999) corresponds to $cc$-universality, or density in the topology of compact convergence, which is also known as the topology of uniform convergence on compact sets. In contrast, the type of universality we have demonstrated is $L^2$-universality, or density in the $L^2$-topology.

The relationships among various notions of universality commonly used in machine learning theory are discussed in detail in the following reference:

Sriperumbudur, Fukumizu, and Lanckriet. Universality, Characteristic Kernels and RKHS Embedding of Measures, JMLR, 2011.

Moreover, it is generally known that once an $L^2$-universal integral representation is established, $cc$-universality of a finite-width model can be shown by employing quasi-Monte Carlo integration (more precisely, by applying the law of large numbers). Therefore, the claims of our work indeed imply $cc$-universality as well.

This paper only handles the infinite width (i.e continuous) setting, and does not provide any quantitative results on how much width is needed for a certain architecture to approximate a target function, akin to the Barron norm in (Barron, 1993).

In our main result, the inverse operator for the integral representation is explicitly obtained. This allows us to apply the so-called Barron’s argument to evaluate the approximation error using the Maurey–Jones–Barron (MJB) bound. In general, applying the MJB bound yields an approximation error of $O(1/\sqrt{n})$ when using a finite-width model with $n$ units.

The implications of this work (such as depth separations between different classes of architectures) is not clear, which limits the significance.

(Please also refer to our fourth response for related discussion.)

In addition, algebraic methods such as Schur's lemma offer a significant advantage: they allow us to assess density (or universality) even when the input and output are not vectors. While there are several classical theorems—such as the Stone–Weierstrass and Hahn–Banach theorems—that provide general tools for determining universality, applying them to neural networks with deep hierarchical structures requires substantial effort and ingenuity.

For example, proof techniques that trace back to Hornik et al. (1989) often rely on repeatedly differentiating activation functions to construct polynomial approximations. While these techniques are mathematically valid, they tend to obscure the underlying mechanism by which neural networks perform approximation, and may not offer much intuitive understanding.

In contrast, conditions such as joint group equivariance and tools like the ridgelet transform, which serves as an inverse operator, provide a more direct and interpretable explanation of how neural networks approximate functions.

The paper could be improved by motivating the various definitions in Section 3 with a concrete example, such as the deep feedforward network.

Thank you for the suggestion. We will incorporate a concrete example, such as the deep fully connected network, immediately after the definition to improve clarity.

Additionally, the universal approximation result for deep feedforward networks in Section 5 is unsurprising, given the universal approximation guarantee for two-layer networks and the fact that deep networks are a strictly larger hypothesis class. Could the authors please comment further on this point?

Thank you for your request. The value of this work does not lie solely in the illustrative example presented in Section 5. Rather, it lies in providing a unified, simple, and constructive principle for analyzing the expressive power of a wide range of learning machines, as demonstrated in Sections 4 through 7.

In deep learning, diverse architectures are proposed on a daily basis. Traditionally, analyzing the expressive power of each new architecture required manual, case-by-case efforts by experts. This study identifies a key condition—joint-group-equivariance—that enables such analysis to be performed systematically. We believe this is where the main contribution of our work lies.

On times the paper uses abstract mathematical language to give alternative descriptions to constructions which may obfuscate the reading (for example some category-theoretical parallels, whose validity I cannot testify). However, I find them redundant/complementary to the actual message of the paper, and conditioned that they are true, they do not alter its story.

Thank you for the suggestion. We will retain the mathematically detailed supplementary explanation as an optional message intended for readers with a strong background in algebra or representation theory. Since it is strictly supplementary, skipping it will not affect the main narrative or the overall understanding of the paper.

The unification under the generalized model is theoretically appealing, however I am not sure if the generalized model (joint-group-equivariant machines) are any further useful. It is not clear to me what is the impact of the unification of mostly known results. Have we learnt something insightful about machine learning, or generalization, in the process of unifying universality theorems?

The main theorem of this work is not merely a unification of existing results; a key strength lies in its ability to systematically and mechanically assess universality even for novel architectures. For example, it enables the straightforward design of expressive networks with universal approximation capability, such as quadratic networks.

In the era of large language models, the diversity of proposed architectures has significantly increased. Manually analyzing the expressive power of each new model on a case-by-case basis is no longer feasible from a theoretical standpoint. Our framework addresses this challenge by offering a general principle.

In particular, algebraic tools such as Schur's lemma provide a notable advantage in that they allow us to assess universality (or density) even when the inputs and outputs are not vectors—something that traditional techniques often struggle with. While classical theorems like the Stone–Weierstrass or Hahn–Banach theorems offer generic tools for establishing universality, applying them to deep neural networks with hierarchical structures requires considerable ingenuity.

By contrast, proof techniques originating with Hornik et al (1989), which rely on repeatedly differentiating activation functions to construct polynomial approximations, often obscure the intuitive mechanism by which neural networks perform approximation. In comparison, our use of joint group equivariance and ridgelet transforms as inverse operators provides a more direct and interpretable understanding of the approximation process in deep networks.

Regarding generalization: Theoretical analysis of generalization error is often based on estimates of the Rademacher complexity of the hypothesis class. However, in deep learning, the Rademacher complexity typically scales exponentially with network depth. This is at odds with practical observations, where deeper networks tend to generalize better.

This discrepancy arises from the limitations of current techniques for analyzing composite functions: the reliance on coarse Lipschitz estimates leads to overly pessimistic bounds. To address this gap, we revisited expressive power analysis and developed the deep ridgelet transform as a theoretical framework that can precisely handle compositions of functions.

The depth-N fully connected neural network described in Section 5 is different that what the community is used to and it looks more general. Does the provided formulation of fully-conntected NNs generalize a ReLU layer for example?

Yes, the presented example extends typical networks, and especially it includes the case when $\sigma$ is ReLU.