Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies approximation power of (residual) vanilla convolutional networks. The authors show that any translational equivalent/invariant mapping/functions can approximated by such networks, in the $L^p$ sense, if 
- the number of channels is at least 2. 
- the kernel size is at least 2 (in each coordinates)
- the network is sufficiently deep (essentially, infinitely many of layers)   

The authors approach this problem from a dynamical viewpoint by viewing CNNs as a discretization of a certain equivalent flow. Although the results is not surprising, the proof is quite technical and non-trivial owing to the number of channels is small (>=2.) 
strength_and_weaknesses: # Strength 

- The overall mathematical clarity of the paper is far above typical ML conference papers. 
- Both the results and proofs are non-trivial. 

# Weaknesses: 
- the results are not surprising (as what was expected). The problem can be much simpler if allowing more channels (shallower networks) vs. the current setup ( == narrow + deeper). 
- The contribution mainly lies in theory and is not very relevant to practice, as it essentially requires the depth of the network to be infinite. 



clarity,_quality,_novelty_and_reproducibility: A few minor remarks.

1. I would like to know more about the technical difference between the current paper (with group equivalent) and Li et al., 2022a;b. Is it possible to `reformulate` the current problem in the quotient space $\mathbb R^k /\mathcal T$, where $\mathcal T$ is the group generated by translations and consider flows defined in this quotient space? 
2. Another related question. Is the problem much simpler if the kernel can have full support? Is it hard to show that any one-layer convolution kernel (with full support) can be approximated multi-layer with Conv + activation with kernel size 2?  
3. Can the problem be reduced to $\mathbb R$ from $\mathbb R^k$, namely, is the problem essentially a 1-D problem? 


summary_of_the_review: update

Thanks a lot for the detailed and insightful reply. I will keep my score. 

------

Although the results of the paper is not surprising, it resolves an important theoretical question regarding approximation power of shallow-and-deep CNNs. I think the result and its proof technique are valuable to the ICLR community.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Universal approximation results in deep learning stated that certain class of neural networks can approximate any function up to arbitrary low error. These results were originally proven for sufficiently wide networks but have been extended in 2 directions:
1. Proving them for small width networks (with arbitrary depth). For example, the work of Lu et al. 2017.
2. Proving them for invariant (equivariant) functions and for corresponding  invariant (equivariant) networks. For example, the work of Yarotsky 2018.

This paper combines these two extensions for shift invariant (equivariant) functions and FCNNs (or residual FCNNs). They prove that FCNNs of constant width can approximate any shift invariant (equivariant) function. They further show that the constant width they show this result for is tight.



strength_and_weaknesses: The authors do not provide intuition for the universal approximation result in the main body of the paper or in the Appendix. The authors should also describe what are the new ideas that go in the proof and what techniques are borrowed from earlier works, this will make the proof easier to verify. For example, in appendix B.5 (Proof of proposition 3) the authors use the approach of dividing the input space into small cubes which has been used in earlier works such as Lu et al. 2017. Same holds for the ‘coordinate zooming function’ which was used in Li et al. 2022.



Other comments:
1. ‘Deep, rather than wide, neural networks are thus a promising solution to this dilemma, using layer composition in the depth direction to build complexity, whereas each layer can be kept sufficiently simple to respect symmetry constraints.’ I do not see why wideness of the layers would have any effect on the symmetry constraints.
clarity,_quality,_novelty_and_reproducibility: As mentioned earlier the paper does not provide intuition for the proof and does not compare the proof techniques with related works. Other than that the paper is well-written.
summary_of_the_review: As the authors do not provide a comparison of techniques with prior works and a description of new ideas that go into their main result I cannot recommend acceptance.

Due to the lack of intuition provided in the paper and my unfamiliarity with the techniques used I was unable to verify the correctness of the proof (given in the appendix) of the main universal approximation result.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies universal approximation of invariant functions, using fully convolutional networks with small filter size, small number of channels, but large depth. The theory is based on dynamical systems, using flow maps to construct deep residual networks approximating the target function, and follows previous work by Li et al, which studied such techniques on non-convolutional architectures.
strength_and_weaknesses: The paper makes interesting contributions to the line of work on approximation via dynamical systems, in particular, it extends previous work by Li et al to showing universal approximation results with convolutional networks with small filters, while Li et al. was restricted to full-width filters.

While this contributions can be of interest, it is nonetheless quite marginal and incremental over previous work, and may not be sufficient by itself for publication.

Here are some suggestions on what could strengthen the paper:
- approximation and statistical rates: the architecture used here is presumably more parameter-efficient than in other works -- can this be used to establish improved statistical rates?

- benefits of this architecture: are there specific function classes where such an architecture is particularly beneficial compared to full-width convolutions, or even fully-connected models?

- better comparison to related work on approximation with convolutional networks, e.g. [this](https://arxiv.org/abs/1611.00740), [this](https://openreview.net/pdf?id=dgxFTxuJ50e), [this](https://arxiv.org/abs/1708.06633), [this](https://arxiv.org/abs/2106.08619), [this](https://arxiv.org/abs/2102.10032), [this](https://arxiv.org/abs/2112.05611) (the last three are for convolutional kernels / infinite-width networks)

clarity,_quality,_novelty_and_reproducibility: ok
summary_of_the_review: Interesting result, but not useful enough by itself.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper analyzes the capacity of narrow but deep CNNs to universally approximate shift-invariant functions, concluding that sufficiently deep CNNs with kernel and channel size greater than or equal to 2 can do so. The analysis is based on dynamical systems and flow maps and follows previous work for non-convolutional architectures.

The reviewers acknowledged that both the proofs and the results were non-trivial, and they found strength in the exposition and mathematical clarity of the presentation, though the intuition behind the approach may need further clarification. Some reviewers found the contributions to be marginal and somewhat incremental compared to prior work, and others questioned the practical relevance of infinite-depth limits.

During the discussion, it was suggested that the results are not surprising. This subjective judgement is debatable and does not fold into the decision; however, the underlying sentiment underscores the main weakness of the paper -- the results in this paper are unlikely to have significant impact on the field, even among theorists working in this direction. The conclusions do not break new ground, the techniques are not novel, and the practical implications are unclear. Having said that, it seems the results here are of high mathematical quality and might fit well at another venue.
justification_for_why_not_higher_score: The results and conclusions of this paper are fairly narrow and represent relatively incremental advances over prior work. The reviewers did not feel like this paper would have significant impact on the community.
justification_for_why_not_lower_score: N/A.
Decision: Reject