Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper considers a certain generalization of convolutional neural networks and equivariant linear networks to the infinite dimensional case, while covering also the discrete case, and offers a universality result. In more detail, the paper first characterizes  equivariant maps as the unique  extensions of "generator", namely regular maps that provide target functions (or vector) defined over a basic domain. In other words, any map that takes functions (or vectors) into functions (or vectors) defined over the representatives from the symmetry's equivalent classes can be extended uniquely to an equivariant map by enlarging its target domain according to the equivariance rule. Second, infinite dimensional fully connected networks (FNNs) and general (equivariant) convolution neural networks (CNNs) are described. The main result of the paper is the Conversion Theorem (Theorem 11), and its consequences. The theorem specify the conditions under which an FNN can be approximated by a CNN. Since FNNs are known to be universal this implies universality of CNNs.  

I think the general CNN formulation and the Conversion theorem are of merit but i think the paper should undergo a rather serious revision before ready for publication. The main issues (that are detailed below) are: the paper does not sufficiently relate the discussed model or the universality results to previous or concrete models (set and graph NN, equivariant group NN, other unused but potentially useful variations), it does not provide sufficient explanation and justification to the different conditions in Theorem 11, there are some details in the proof and the description of Theorem 11 which are missing/unclear, Theorem 16 has some unclarity. I think attending these will provide a much more accessible and useful paper for the community.

DETAILS.

> Relations to previous work. The paper discuss a rather broad generalization of equivariant network (equations 4 and 5). I think exploring the relations to existing generalization to convolution neural networks and equivariant networks is in order. For example, when taking $\mathcal{S}=\mathcal{T}=[n]$ ($[n]=\{1,2,...,n\}$) and $G=S_n$ (the permutations of $[n]$) equation (4) seems to boil  down to  Deepsets of Zaheer et al. mapping $\mathbb{R}^n\rightarrow \mathbb{R}^n$ equivariantly. Does theorem 1 implies that Deepsets (as equivariant model) is universal (as was proved in several previous works)? In this case, Theorem 3 states that any function $f_1(x)$ can be extended to be equivariant via $f_j(x)=f_1(g\cdot x)$, where $g$ is a permutation such that $g(j)=1$. If this is all required for universality proof this would be a great simplification over previous proofs. This example could help the reader grasp this extension and also relate to previous works on equivariant learning.  What can be said about the equivariant tensor models and graph neural networks using the universality result in this paper? What can be said about the negative results of universality of second order (or higher order) tensor graph networks? Does the method in this paper imply group convolution networks are universal?  Are there any instantiations of the CNN discussed in this paper that are useful although not discussed in previous work? In summary, how the results in this paper relates to known and unknown results of CNN generalizations and what universality proof does it generalize? 

> Theorem 11. First, looking at the proof, I feel there is a condition of the FNN $\phi$ that is missing from the theorem's formulation. That is, that the different layers of $\phi$ should be mapping to and from functions on base domains of $G$, $\mathcal{C}(\mathcal{B})$. Without it I can't see how the extension to equivariant maps work. How is it guaranteed that $\phi$ can be extended if internal states are defined on non-base domains? If this is true then how the FNN found from the universality result of FNN (e.g., Theorem 12 and 14) are guaranteed to satisfy this condition? Related to that, I couldn't exactly understand the claim of the second to last layers in the proof of Theorem 11: the first layer outputs a function in $\mathcal{C}(G/H_\mathcal{T}\times \mathcal{B})$, but the second layer of the FNN maps functions from some different domain $\mathcal{C}(\mathcal{B}_2)$. If I understand correctly, the idea of the proof is basically using the extension mechanism of Theorem 3 to extend mapping to functions over base domains to equivariant mappings. This seems to produce a sort of lift in the domain of the target function at every step. Is that correct? Can you provide the proof for a simple example of equivariant networks such as Deepsets? Minor: there are some wrongs equation references in the proof of Theorem 11.

> The condition (C1) in Theorem is not clear to this reviewer. I think some examples and explanation should be provided. I could not really figure out, despite the following paragraphs, in what situations can we verify this condition and in what sense it limits the scope of the theorem. Is there a simple intuition or a way to check such subgroups exists? Are these normal subgroups?  Should $H_\mathcal{T}$ be a strict subgroup of $F_{\mathcal{S}}$? Is this condition holds in standard cases such as $[n]$ and $G=S_n$, or images and $90$ degrees rotations? Does it mean $\mathcal{S}$ has to have a group structure? 


> In Theorem 16: How  do we make sure the first layer can be seen as a generator? Can we given $[N]$ the required base structure? Is $[N]$ a base domain of $G$ necessarily? This also relates to the question I asked above about the condition in Theorem 11. Anyway, this proof should be provided in the paper or supplamentary. 

> The authors mention that the invariant case cannot be handled. However, invariant functions can be made equivariant by considering the trivial representation, e.g., in the discrete case let $f(x)$ be invariant to $S_n$, then $f_i(x)= f(x)$ for all $i\in [n]$ is equivariant I believe. Can we approximate this equivariant function? 

review_title: Nice formalism, connection to previous models and some details not clear

final_score: rating: 5: Marginally below acceptance threshold
review_content: After discussions:
I read the author's response and other reviews. The authors made a considerable effort to address my concerns. As a result, the paper has improved and I increased my score. 

Having said that, I am still not sure that the paper is ready for publication in its current form. My main concern is still the accessibility/readability of the results in this paper, which I think can be further improved for the benefit of both the community and the authors (more accessible paper => more imapct). To conclude, the results in this paper are interesting and are strong enough to warrant a publication, but the paper can really benefit from another revision.
 
Summary:

The paper studies the approximation power of equivariant neural networks in a very general setup: the input space is assumed to be a function space (compared to a finite-dimensional space in standard setups) and the group is assumed to be any locally compact group. The main theorem shows how to convert fully connected networks to equivariant networks. This is then used to derive universal approximation theorems from the well-known results on fully connected networks. The paper seems to suggest an interesting approach and the results seem significant but the paper is very hard to follow and I am not sure I understood it. See the comments below.

Strong points:

Important problem - invariant/equivariant models provide a very helpful inductive bias for many tasks on symmetric inputs. Understanding their approximation power is crucial.
The idea of the main theorem, i.e. converting and FNN to CNN is new and might be useful.


Weak points:

The paper is written badly and is very hard to follow. (1) the intro does not give enough information about what is actually done in the paper. The first time you see the contributions are in a short list at the end of the section. It is very hard to understand them this way. (2) Section 2.2 is unnecessarily overcomplicated and difficult to read, partially due to excessive notation. I think that the basic idea of this subsection can be written in a much simpler way. Discussing the invariant case might also help. I would also suggest rewriting the paper in the following way: start with S,T finite and present all the results. Then discuss the generalization to infinite S,T (which are less useful in my opinion).
General comment: *Please add examples* - this will help the reader follow the paper. Perhaps choosing a particular case of S,T an G and exemplifying any result in the paper on this setup can be useful.
Relation to prior work is not discussed. What is the relation of theorem 13 to the results obtained by Maron, Keriven and Ravanbakhsh? Specifically, these works show that in some cases high order tensors are needed for universal approximation by invariant neural networks - can this result be recovered from your results?

Recommendation: 

The results in this paper seem strong and important, but in its current form it cannot be accepted. I recommend a significant revision of the paper to make it more readable. I would be happy to increase my score (and confidence) in this case.


Minor comments:

There are many typos in the paper. 
P. 2 - replace subrepresentation with subgroup?

review_title: Important problem, interesting results but very hard to follow

final_score: rating: 7: Good paper, accept
review_content: The paper proves a universal approximation theorem for equivariant maps by group convolutional networks in an extremely general setting. The proof applies to discrete and continuous settings, including infinite dimensional ones. 

The general idea of the proof is as follows. First, it is shown that an equivariant map is determined by its generator, i.e. its values on the orbits (so far, not surprising). This means that one only has to prove universality for the generator. Universality is then proved for the generator by a fully connected network, and separately an approximation theorem of FCNs by CNNs is proved.

Proving a result of this generality is technically very challenging. Although I am not a professional mathematician, I know that there are many pitfalls when proving results like the one in this paper. For instance, the orbit space can be topologically very complicated. Having spent about a day with this paper, I think that at least the general idea of the proof is sound, and the authors have sidestepped several technical problems I could think of using well chosen technical assumptions. My knowledge of topology and analysis is not sufficient to fully vouch for the technical correctness in every detail though.

Universal approximation theorems are considered to be an important kind of result, and this paper proves a very general one for equivariant maps. Provided the other reviewers do not surface any technical concerns I would recommend acceptance.


Typos and minor issues:
- "AAmong"

- I would recommend not putting a numbered footnote at the end of an equation, as it could be read as a power. E.g. mu_phi << nu^5. Better to put the footnote after the last English word or something like that. 

- On condition C1: if H_S represents the stabilizer subgroup and this group is the same at all points, then it seems to me the condition is similar to assuming that S is a homogeneous space for G, as has often been done in previous work. Would it be possible to just make that assumption?

----
Update:
I do agree with the other reviewers that the paper may be difficult to read, especially for non experts. Nevertheless I still think the paper makes a nice contribution, so I will keep my rating.
review_title: Review

Meta-review: This work studies the question of universal approximation with neural networks under general symmetries. For this purpose, the authors first leverage existing universal approximation results with shallow fully connected networks defined on infinite-dimensional input spaces, that are then upgraded to provide Universal Approximation of group-equivariant functions using group equivariant  convolutional networks. 

Reviewers were all appreciative of the scope of this paper, aimed at unifying different UAT results under the same underlying 'master theorem', bringing a much more general perspective on the problem of learning under symmetry. However, reviewers also expressed concerns about the accessibility and readibility of the current manuscript, pointing at the lack of examples and connections with existing models/results. Authors did a commendable job at adding these examples and incorporating reviewers feedback into a much improved revision. 

After taking all the feedback into account, this AC has the uncomfortable job of recommending rejection at this time. Ultimately, the reason is that this AC is convinced that this paper can be made even better by doing an extra revision that helps the reader navigate through the levels of generality. As it turns out, this paper was reviewed by three top senior experts at the interface of ML and groups/invariances, who themselves found that the treatment could be made more accessible --- thus hinting a difficult read for non-experts. In particular, the main result of this work (theorem 9) is based on a rather intuitive idea (that one can leverage UAT for generic neural nets on the generator of an equivariant function), that requires some technical 'care' in order to be fleshed out. The essence of the proof can be conveyed in simple terms, after which following through the proof is much easier. Similarly, the paper quickly adopts an abstract (yet precise) formalism in terms of infinite-dimensional domains, which again clouds the essential ideas in technical details. While the paper now contains several examples, this AC believes the authors can go to the extra mile of connecting them together, and further discussing the shortcomings of the result --- in particular, the remarks on tensor representations and the invariant case are of great importance in practice, and should be discussed more prominently. Finally, while this work is only concerned with universal approximation, an important aspect that is not mentioned here is the quantitative counterpart, ie what are the approximation rates for symmetric functions under the considered models.  

Decision: Reject