Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper under review studies the universal approximation theory with constraints. 
For any convex or non-convex compact set, a universal approximation is proved through a probabilistic transformer with constraints. Furthermore, a chart-free universal approximation is established on the Riemannian manifold with geodesically-convex constraints.
main_review: 1. The paper shows the first universal approximation with constraints. The general theory shows that the universal approximation can use the probabilistic transformer to project the outputs in the set $K$. In particular, the probabilistic transformer helps to deal with non-convex constraints in Euclidean space and the geodesic convex constraints in non-Euclidean space, I.e., Riemannian manifold.

2. The geodesically convex constraint seems to be an interesting and promising idea to treat non-convex constraints in the Euclidian space. The assumption on the sectional curvature is uniformly bounded above. Is there any connection that can be said in this case under Ricci curvature tensor? 

3. The paper is technically well presented. However, there are still some typos. The authors need to improve their writing. 

4. It would be a good idea to provide more examples to demonstrate the general theory. 

summary_of_the_review: The paper seems to address a well-known important class of problems. The universal approximation theorem might make significant impacts in solving optimization problems with constraints.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper intends to provide a stronger type of universal approximation result of transformer models. However, more details on experiments is required with a major revision of presentation and clarity.
main_review: Strength: + Provides rigorous theory to support the utility of transformers for deep neural network based predictive purposes under constrained settings.
+ Soft constraint set that is defined using available data points is an interesting aspect that the paper considers. In fact, the authors were able to extend their theory to show that transformers can be used to model any data dependent constraint sets as well.
+ Results of this paper may be applicable to practical use cases.
Weakness: - The paper is hard to follow at many places since only informal theorems are provided throughout the paper.
- The main theorem 2.2 is suboptimal -- optimal network may require width greater than the number of input dimensions n. For image analysis, this corresponds to the number of pixels.
-Confusing notations.
- No experiments to verify any of the quantitative results.

summary_of_the_review: Justification: The constraint examples are too unnatural. For example, in geometric deep learning, authors argue that when K is a disjoint set, then the closest point computation becomes an unmanageable dilemma, claiming that the linear relaxations are meaningless for integer program (IP) while LPs are routinely used to solve IPs in practice using a branch and bound scheme. While some pieces of notations are kept constant throughout the paper, there are many confusing notations at various places that can easily be avoided - "Attention" in eq (4) is different from "attention". Adding to this issue, another central issue with the presentation is that all the technical statements in the main paper are Informal theorems with no rigorous explanations provided. This makes it very hard to read the paper because while the statements themselves may be locally correct or correct in isolation, it sometimes does not even make sense when put together as a whole, and makes it possible to verify the technical correctness of the paper. Somewhat related to the previous point, some technically deep concepts (such as Wasserstein-1 distance) are introduced in passing and handled in a slightly cavalier manner. It could have been nice if the authors provided some explanations to the figures -- at the moment, the reader has to guess what the authors intend to say. 

Given that the paper shows quantitative results in the infinite sample setting, it is not clear whether the results hold in the finite sample setting where transformers are being used in practice. It would have been nice if the authors can formulate and show some toy experiments to even check whether such universality may be possible for dataset in the hands of a practitioner.

After response: Thanks for the detailed response. I agree with the modifications, revisions, additional sections, and references proposed in the response. These changes were really helpful in parsing the paper for me since I have adequate mathematical background, but not so much experience in theoretical computer science. With more clearer notations, and figure descriptions, I can now see that the paper indeed focuses on universal approximation rather than generalization, and now I feel that my criticism about finite sample settings has been answered by the toy experiments also.  I choose the option of "minor issues" in correctness only because some statements still read handwavy in Section 1, for example, there are many places where the authors use the word "any", as in, any loss function, any constraint set, any goood activation etc.. While it may be correct in some sense, I find it odd to use in an otherwise rigorous paper. As an aside, I would like to point out this certainly does not hold if one wants to train from scratch since we know that loss functions and activation functions have a significant effect on first order algorithms. Thanks for providing additional references for us to check, and while going through them I found that some of the theoretical papers have very relevant practical use cases and I believe that they may add significant value to the overall scope and presentation given here, for example, Meta-learning with implicit gradients. I have raised my score.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: This paper presents a family of constrained universal approximation results for probabilistic transformers.  The authors provide significant theoretical contributions for both convex and non-convex constraint sets.  In my opinion, this represents a significant advance in our understanding of universality in ML.
main_review: ### Strengths

**Examples.**  Throughout the paper, the authors give numerous examples to illustrate why and how one might have constraints when training neural networks.  These were quite helpful in giving intuition for the (rather technical) contents of the paper.  This is a model I wish more technical papers would follow, as it allows even non-technical readers to get an idea of what the theory is all about.  Further, the authors do a commendable job of relating this work to the statistical results which have recently been proposed.  

**Problem statement & setting.**  The problem statement is really clearly articulated.  The idea of providing a universal approximation property under constraints seems quite natural, and the authors motivate it extremely well.  Indeed, it is true that there are many works that argue for constraints in deep learning without considering the question of whether satisfying such constraints is even possible.  

**Technical quality.**  I was not able to read through all of the proofs, especially given that the appendix gets pretty involved.  However, from what I saw, the proofs are of high quality.  Indeed, the generalization to the case of nonconvex K seems quite involved.  The proof techniques used here should be of wider interest.

**Informal theorem presentation.**  The choice to first state the main results informally greatly helped the readability of the paper.  The main results are also illustrated with useful diagrams.  

**Novelty.**  This is the first result of this kind that I am aware of.  For this reason, I believe that this paper has a significant claim to novelty.

**Experiments.**  I like the experiments at the end of the appendix as well.  This helps to cover another natural question regarding how one can use these results in practice.

### Weaknesses

**On the attention module.**  I think the paper could benefit from further explaining why this particular form of attention is natural.  It would also perhaps help to illustrate this with an example.  As the credibility of the paper relies on the reader accepting that this attention model is natural and general enough to form the basis of the approach to universal approximation, I think that it's worth spending some more time here.  In particular, I didn't get a good sense of the role of the matrix $Y$ in build up to Informal Theorem 1.  

**Figures.**  Don't get me wrong, I love that there are figures here.  However, I think that they could be explained better.  For instance, it wasn't clear to me what the green region was in Figure 1.  Is this $K$?  Also, the blue dot seems too small, and thus quite hard to see.  
summary_of_the_review: My review for this paper is rather short because overall I think that this paper is excellent.  It's clear that the problem is well-motivated and there are few results in the area.   To this end, the authors provide highly technical results to specifically address this novel and important question.  Moreover, the authors make a great effort to explain their results to a non-technical audience.  This is a clear accept in my opinion, and should be highlighted at the conference.
review_title: null

Meta-review: The paper studies an interesting question of whether neural networks can approximate the target function while keep the output in the constraint set. The constraint set is quite natural for  e.g. multi-class classification, where the output has to stay on on the probability manifold. The challenge here is that traditional universal approximation theory only guarantees that $\hat{f}(x) \approx f(x)$, but can not guarantee that $\hat{f}(x)$ lies exactly in the same constraint set as $f(x)$.

The paper made a significant contribution in the theory of deep learning -- It is shown that the neural network can indeed approximate any regular functions while keep the output stay in the regular constraint set. This gives a solid backup in terms of the representation power of neural networks in practice, to represent target functions whose outputs are in certain constraint set (e.g. probabilities).
Decision: Accept (Spotlight)