On the Universal Approximation Property of Deep Fully Convolutional Neural Networks
Authors: Ting Lin
Zuowei Shen
Qianxiao Li
Venue: Submitted to ICLR 2023 (2023)

Abstract:     We study the approximation of shift-invariant or equivariant functions by deep fully convolutional networks from the dynamical systems perspective. We prove that deep residual fully convolutional networks and their continuous-layer counterpart can achieve universal approximation of these symmetric functions at constant channel width. Moreover, we show that the same can be achieved by non-residual variants with at least 2 channels in each layer and convolutional kernel size of at least 2. In addition, we show that these requirements are necessary, in the sense that networks with fewer channels or smaller kernels fail to be universal approximators.

Under review as a conference paper at ICLR 2023
ON THE UNIVERSAL APPROXIMATION PROPERTY OF DEEP FULLY CONVOLUTIONAL NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the approximation of shift-invariant or equivariant functions by deep fully convolutional networks from the dynamical systems perspectíve. We prove that deep residual fully convolutional networks and their continuous-layer coun- terpart can achieve universal approximation of these symmetric functions at con- stant channel width. Moreover, we show that same can be achieved by non- residual variants with at least 2 channels in each layer and convolutional kernel size at least 2. In addition, we show that these requirements are necessary. the sense that networks with fewer channels smaller kernels fail to be universal approximators.
INTRODUCTION
Convolutional Neural Networks (CNN) are widely used as fundamental building blocks in the design of modern deep learning architectures, for it can extract key data features with much fewer param- eters, lowering both memory requirement and computational cost. When the input data contains spatial structure, such as pictures or videos, this parsimony often does not hurt their performance. the case of fully convolutional neural networks (FCNN) (Long
This is particularly interesting al., 20155, built by the composition of convolution, nonlinear activation and summing (averaging) layers, with the last layer being a permutation invariant pooling operator, see Figure Consequently,
Inout:
FCNN
x
FONN
64 64
FCNN
x
-Poding
Output
3864 x
3864 x
3"3 conv
64
Layers FCNN Block
Figure illustration of fully convolutional neural network.
a prominent feature of FCNN that, when shifting the input data indices (e.g. picture, video, or other higher-dimensional spatial data), the output result should remain the same. This called shift invariance. An example application of FCNN is image classification problems where the class label (or probability, under the softmax activation) of the image remains the same under translating the image (i.e. shifting the image pixels). A variant of FCNN applies to problems where the output data has the same size as the input data, e.g. pixel-wise segmentation 2017). In this case, simply stacking the fully convolutional layers is enough. We call this type of CNN equivariant fully convolutional neural network -CNNF,,), since when shifting the input data indices, the output data indices shift by the same amount. This is called shift equivariance. It is believed that the success of these convolutional architectures hinges on shift invariance or equivari- ance, which capture intrinsic structure in spatial data. From approximation theory viewpoint, this
images (Badrinarayanas et al.)

---

Under review as a conference paper at ICLR 2023
presents delicate trade-off between expressiveness and invariance: layers cannot be too complex to break the invariance property, but should not be too simple that it loses approximation power. The interaction of invariance and network architectures are subjects of intense study in recent years. For example, Cohen & Welling (2016c) designed the steerable CNN to handle the motion group for robotics. Deep sets (Zaheer et al. (017) are proposed to solve the permutation invariance and equivariance, Other approaches to build equivariance and shift invariance include parameter sharing (Ravanbakhsh et al. (017)) and the homogeneous space approach (Cohen & Welling [016b) Cohen et 2019). See Bronstein et al. (2017) for a more recently survey. Among these architectures, the FCNN is perhaps the simplest and most widely used model. Therefore, the study of its theo- retical properties is naturally first and fundamental step for investigating other more complicated architectures.
In this paper, we focus on the expressive power of the FCNN. Mathematically, we consider whether a function F can be approximated via the FCNN (or eq-FCNN) function family in I." sense. This is also known universal approximation in LP. In the literature, many results on fully connected neural networks can be found, e.g. Lu et al. (2017); Yarotsky (2018a); Shhnn et al. (2019). However, relatively few results address the approximation of shift invariant functions via fully convolutional networks. An intuitive reason is that the symmetry constraint (shift invariance) will hinder the un- conditioned universal approximation. This can be also proved rigorously. In Li et al. (2022b), the authors showed that a function can be approximated by an invariant function family to arbitrary accuracy, then the function itself must be invariant. As consequence, when we consider the ap- proximation property of the FCNN, we should only consider shift invariant functions. This brings new difficulty for obtaining results compared to those for fully connected neural networks. For this reason, many existing results on convolutional network approximation rely on some ways of break- ing shift invariance, thus applying to general function classes without symmetry constraints (Oono) & Suzuki 2019). Moreover, results on convolutional networks usually require (at least one) layers to have a large number of channels.
In contrast, we establish universal approximation results for fully convolutional networks where shift invariance is preserved. Morcover, we show that approximation can be achieved by increasing depth at constant channel numbers, with fixed kernel size in each layer. The main result of this paper (Theorem] D shows that if we choose ReLU as the activation function and the terminal layer is chosen general pooling operator satisfying mild technical conditions (e.g. max, summation), then convolutional layers with at least 2 channels and kernel size at least can achieve universal approximation of shift invariant functions via repeated stacking (composition). The result is sharp in the sense that neither the size of convolution kernel nor the channel number can be further reduced while preserving the universal approximation property.
To prove the result on FCNN, we rely on the dynamical systems approach where residual neural networks are idealized as continuous-time dynamical systems. This approach was introduced in E (2177) and first used to develop stable architectures (Haber & Ruthotto 2017) and control- training algorithms (Li et al. 2018). This is also popularized in the machine learning literature as neural ODEs (Chen et al. 2018). On the approximation theory front, the dynamical systems approach was used to prove universal approximation of general model architectures through compo- sition (Li et al., (022a).. The work of et al. (2022b), extended the result to functions/networks with symmetry constraints, and as a corollary obtained a universal approximation result for residual fully convolutional networks with kernel sizes equal to the image size. The results in this paper restrict the size of kernel in a more practical way, and can handle common architectures for applications, which typically use kernel sizes ranging from - 7. Moreover, we also establish here the sharpness of the requirements on channel numbers and kernel sizes.
The restriction on width and kernel size actually can provide more interesting results in the theo- retical setting. This is because if we establish our approximation results using finite (and minimal) width and kernel size requirements. they can be used to obtain the universal approximation property for a variety of larger models by simply showing them to contain our minimal construction.
In summary, the main contributions of this work are as follows:
1. We prove the universal approximation property of both continuous and dine-disreetized fully convolutional neural network with residual blocks and kernel size of at least 2. This result concerns about the deep but narrow neural networks with residual blocks. We provide
2

---

Under review as a conference paper at ICLR 2023
sufficient condition result about the universal approximation property with respect to the shift invariance. The result does not rely on the specific choice of nonlinear activation functions, nor the choice of the last layer.
2. Further, we prove the universal approximation property of fully convolutional neural net- work with ReLU activations having no less than two channels each layer, and kernel size of at least 2.
3. Finally, we show that the channel number and kernel size requirements above are sharp, since further reducing them may lose the universal approximation property.
4. The above three points hold true for the approximation of shift equivariant mappings via eq-FCNN.
The paper organized as follows: Section introduces the mathematical formulation and the main results of this paper. Section 3 introduces the main analytical tool and the bridging result in this paper for the positive part of the main theorem, while Section 4 and proves the sharpness part of the main theorem. The discussion and conclusion is shown in Section 6 In Appendix [ we provide the shift equivariant result, and the remaining technical proof are collected in Appendix B
FORMULATION AND MAIN RESULTS
In this section, we introduce the notation and formulation of the approximation problem, and then present main results. We first recall the definition of convolution. Consider two rank tensors a and y E X, where X == _21 x x Rd We denote by n [M1,..., nal the data dimensions, and define the convolution of æ, y by
y with
[2]
Σ
ar s fyll+ss-
Here, i are multi-indices (beginning with 1) and the arithmetic uses the periodic boundary condi- tion. Taking æ E R3x3 3 as an example, we denote
x (1.1)
x (1,2)
(1,3)
a (2.1)
(2.2)
(2.3)
[0] (3.1)
(3.2)
[cc (3.3)
where (z.4( is identified with (.)) and similarly for the other indices.
Let us also define the translation operator Th with respect to multi-index l by [Taaz]; [
The key symmetry condition concerned in this paper shift equivariance can now be stated as the following commuting relationship:
(x * y) = x (Tky).
We now introduce the definition of the fully convolutional neural network (FCNN) architecture we subsequently study. Let
vio vo x +b1),, w0 E X, Us by E TR.
be a function family representing possible forms for each convolutional layer with r channels. Here, (x) max((, 0) is the ReLU function.
Let the final layer be a pooling operation g X obeying the following condition: y is Lipschitz, and permutation invariant with respect to all the coordinates of its input data, i.c. the value of g does not depend on the order of its inputs. Examples of such a pooling operator include summation max, Note that this stronger than just requiring
g(x:) = Σt [x] and max g(x) g to be shift invariant.
In practice, the convolutional kernel used will be more restrictive, say kernel size of 5. To study the effect of kernel size, we define the support for an element æ E X as supp(x)) (x) := (j1.22, ... Jd), where js is the minimal number such that if the multi-index has i, ju for some s, then [m); 0.
3

---

Under review as a conference paper at ICLR 2023
T 0 0
For example, the support of tensor
is (3, Two remarks on this definition of
0
support are in order. First, the element with an element è E R XJaX-"Xja, Second, a convolution kernel with size of can be regarded
E X with supp(æ) و (ji, j2, ... Ia) can be identified
as tensor w with support I 8, s). Thus, we may define the convolutional layer
family with support up to & as
Fr.e == Σ 1, (w; * 6,1), w. E x, supp(w.) S 2,2,,
With these notations in mind, now introduce the following hypothesis spaces defining fully convolutional neural networks and their residual variants
CNN,,6 ,, = [g o fm ..... fi fi,.... fm E Fr,, m 2 21; resCNN,, = ( o (id +mm) ....o (id +f1) f,, fm E Fr... 21
(3)
For any family F of functions - R. let us define F + R == + E F,b E R). This expands the hypothesis space by adding a constant bias to the original function family F. Observe that all functions the families CNN., and resCNN., are shift invariant the following sense.
Definition 1. A function @ X + R. is called shift invariant if ((()) = ((Txx) for all æ E X n. A function family X is called shift invariant for all its member are shift invariant.
A function family X satisfies the shift invariant universal approximation property (shift invariant UAP for short) if
1. The function family X' is shift invariant, and
2. For any shift invariant continuous (or LP) function æb tolerance 0, compact set K C X and p E [1, oo), there exists &p X' such that || (llze(K)
Correspondingly, we define shift equivariance. A mapping X + X is called shift equivariant if <T(Txx)= = (=))))))). We will prove the shift equivariant UAP Appendix
The main result of this paper is as follows.
Theorem (Universal Approximation Property of CNN). The following statements hold:
1. The residual FCNN hypothesis space resCNN, e possesses the shift invariant UAP for r 2 1 and l 2 2. The non-residual hypothesis space CNN,, possesses the shift invariant UAP for r 2 2 and f 2.
2. The kernel size 2 is optimal in the following sense: for l with min f, 1, then neither resCNN x + IR nor CNN + I. possess the shift invariant UAP.
3. The channel-width requirement for non-residual fully convolutional neural network is opti- mal, in the sense that the function family CNN1,.0 + IR. does not possess the shift invariant UAP.
Notice that due the extended hypothesis space from the added bias, the sharpness results are stronger than just implying that CNNx, & or resCNN does not possess the shift invariant UAP. The reason establish the sharpness results for + IR is to ensure that the lack of approximation power does not arise from the fact that the ReLU activation function a has non-negative range. Note that this sign restriction does not affect the positive result, since with at least 2 channels one can produce output ranges of any sign. Although this theorem only considers the approximation of shift invariant architectures, similar result can be established for the shift equivariant architectures. We will discuss detail in Appendix A Furthermore, in this section we restrict the activation function a to be the ReLU function, but this restriction is necessary only for the non-residual case. As will see in Appendix B.4, for residual FCNNs we can relax our requirement on to include a large variety of common activation functions.
In what follows, we define for multi-indices j. the partial order i 2 if i. 2 jx, 8 1, In this paper, we always fix a p (1,
4

---

Under review as a conference paper at ICLR 2023
Theorem Camooremminde Iindicates the following basic trade-off in the design of deep convolutional neural network architecture: if we enlarge the depth of the neural network, then even if we choose in each layer a simple function (in this theorem, 2 channels with each kernel in channel with size of 2), can still expect a high expressive power. However, the mapping adopted in each layer cannot be degenerate, otherwise it will fail to capture information of the input data. The second and third part of this Theorem tells that this degeneracy may come from either channel number or the kernel size (support of the convolutional kernel).
2.1 COMPARISON WITH PREVIOUS WORK
We compare this theorem existing works on the approximation theory of convolutional networks and related architectures. The existing result around the approximation capabilities of convolutional neural networks can be categorized into several classes. One either
takes the kernel as full-size (same size as the input) (e.g. Li al. 2022b which is not
often used in practice,
assumes a sufficiently large channel number in order to adopt some kernel learning methods
(e.g. Biett (202T) | Favero al. (202T): Xiao (2022) averaging methods (e.g. Yarotsky
(2018b); Bao et al. 22019;; Petersen & Voigtlaender 2220 Jiang et al. 2021
removes the nonlinear activation function and reduce to linear approximation problem (e.g. Zhou (2020)) then use complex fully connected terminal layer(s) to achieve approx- imation.
As a consequence, few, if any, results are obtained when the kernel size is small (and the channel number is fixed). Indeed, none of the results we are aware of have considered situations where both kernel size and the width are limited. However, this is in fact the case when designing deep (residual) NNs, as the ResNet family, where the primary change is increasing depth. Our result indicates that even though each layer is relatively simple, much more complicated functions can be ultimately approximated via composition. Furthermore, our analytical techniques (especially for the residual case) does not depend on the explicit form of the activation function and the pooling operator in the last layer.
Another highlight feature of our result is with respect to the shift invariance, which might be over- looked some approximation result for convolutional neural network. We restrict our attention to the periodic boundary condition case, which leads to architectures that are exactly shift invari- ant or equivariant, This significantly confines the expression power of the hypothesis spaces. such symmetry is not imposed on each layer, then one can achieve universal approximation of general functions, but at the cost of breaking shift equivariance. For example, Oono & Suzuki (2019) and Okumoto & Suzuki (02T) drop the equivariant constraints and builds the deep convo- lutional neural network with zero boundary condition, achieving universal approximation property of non-symmetric functions. This because the boundary condition will deteriorate the interior equivariance structure when the network is deep enough. Also, the shift invariance considered here about the pixel (i.e. the input data), while some other attempts like Yang & Wang (2020) build a wavelet- like architecture to approximate a function invariant to the spatial translation, I.e., functions satisfy that f = f( k) for le E
2.2 TECHNICAL NOVELTIES IN THE DYNAMICAL SYSTEMS APPROACH
In this paper, we develop the dynamical systems approach to analyze the approximation theory of compositional architectures first introduced in Li et al. (022a) without symmetry considerations, and subsequently extended to handle symmetric functions with respect to transitive subgroups of the permutation group Li et al. (2022b). While shift symmetry is covered under this setting, the results in Li et al. (2022b) can only handle the case where the convolution filters have the same size as the input dimension.
In contrast, the results here are established for small and constant filter (and channel) sizes. This is an important distinction, such configurations are precisely those used in most practical applica- tions. On the technical side, the filter size restriction requires developing new arguments to show how arbitrary point sets can be transported under flow key ingredient in the proof of universal
5

---

Under review as a conference paper at ICLR 2023
approximation through composition (See Section B.4 for detailed discussion). Furthermore, the restriction on filter sizes also enabled us to address new questions, such as a minimal size require- ments, that cannot be handled by the analysis in Li al. (022b). The results and mathematical techniques for these sharpness results are new. Concretely, to provide a sharp lower bound on the filter size and channel number requirements,
develop some techniques to extract special features of functions in CNN1,, 1, + R and CNN.,, ,1 R that leads to the failure of universal approximation. Detailed constructions are found in Section 4 and Section 5 The construction and the corresponding analysis in this part are nontrivial, and we believe that the examples are also useful in analyzing the approximation property of other architectures.
PART I OF THEOREM I THE DYNAMICAL SYSTEMS APPROACH
The core technique employ analyze both CNN and resCNN is the dynamical systems approach: in which we idealize residual networks into continuous-time dynamical systems. In this section, we introduce the key elements this approach.
We first introduce the flow map, also called the Poincaré mapping, for time-homogenous dynamical systems.
Definition 2 (Flow Map). Suppose f X X is Lipschitz, we define the flow map associated with f at time horizon T as (x) ( (T)), where (() = f(((t)) with initial data =00 = x.
follows from Arnold (173) that the mapping &(f, T) is Lipschitz for any real number T, and the inverse of (J,T) T) is Φ (-, T), hence the flow map is bi-Lipschitz.
Based on the flow map, we define the dynamical hypothesis space for the convolutional neural network. Define the dynamical hypothesis space with convolutional kernel as
CODE,, {g ((fm,bm
(ff: 4) "., Sn E Fr,,,,,.. pm E R). (4)
The following proposition shows we can use residual blocks to approximate continuous dynamical systems.
Proposition 1. Suppose that F is bi- hi-LLipschitz family. For given
T (f(m, bm) ... ( (ffi, fIEF,
and compact K C X, > 0, there exists
t = (id + 9m') ... ... (id +1191,, gi E
for some s; 0, i == 1, .,... I,...,,',,, such that g 2 @(IIP(K) S
The following result shows the shift invariant UAP for the continuous hypothesis space, and its proof can be found in Appendix A
Theorem 2. The dynamical hypothesis space CODE1,2 22 satisfies the shift invariant UAP.
The rough proof strategy is as follows. We reduce the problem to finite point transportation, i.e., we need to show that the hypothesis space can transport arbitrary but finitely many points (in different orbits under the action of the translation group) to any other set of points. This is done in the previous work of Li et al. 2022b). A key technical difficulty here is that the kernel size is limited, thus previous known constructions of point transportation (Li et al. (202b)) cannot achieve this. Here, show that can employ more composition of layers to construct auxiliary mappings to achieve this transportation property. The intuition is that finite-size kernels (satisfying some minimal requirements), when stacked many times, is good as full-sized kernel for domain rearrangement a key enabler of universal approximation through composition.
With this theorem hand, we now prove the first part of Theorem
Proof of the first part of Theorem 7 By the straightforward inclusion relationship, it suffices to show that the function family resCNN1. and CNN2,2 have UAP. For the residual version, follows from Proposition T that if CODE1 satisfies UAP, then so does resCNN In other words, a convergent time discretization inherits universal approximation properties. Thus, given Theorem 2 it suffices prove the remaining CNN case.

---

Under review as a conference paper at ICLR 2023
We begin with weaker result, showing that CNN satisfies UAP. We prove that resCNN1,, C CNN For given f = =vo w * + b1) with o = ReLU, we write
I x+ f(x) = [a + (-1) + vo x b1).
This relation indicates that resCNN 3NN 3,2. which means that 3NN has UAP.
However, this approach cannot handle the case CNN22.2 since the inclusion rcsCNN1,2 C 2NN2,2 does not hold. This leads to further modification.
In the following, we prove that for a given G E resCNN1122 compact K C X, there exists H E 2NN2, such that (xx) G(x)) for all x K. Suppose that G = g o fM o fi, where f(()) = + r'o(w' + - b'). Set = f. o....... f1, " id and note that each Y is a Lipschitz mapping. We now consider sufficiently large real number R such that hx( S R holds for all i = 0, 1. .M and x E K. This can be done since each %/2 is Lipschitz, and K is compact
set. Define
uo(æ)) ol + R1),
(5)
and
(x(x)) (xx + v''lww' x + (b' (En[w")) R)) F2,2
(6)
for i = 1, ... M.. Similarly, define ny (x)= = U. .... u1 un. Clearly, E 2NNN2, for all 2 0. We now prove by induction that
n:(x)) = (x)) ) + R1 for = 0, 1, ... ,M.
The base case (i 0) is obvious from the definition that (7) holds for i, then
since x + R1 > 0 for all x E K. Suppose
7 (x) =0 (x) + R1) + u'o * (m(x)+ + R1) + (6' - (Ex [[][ww))))) R))
(x) + R1 + v'a(ww ((m)++++ b1))
- + R1.
The first equation uses the definition of (6) and the second equation follows from (x) + R1 > and w' R1 = (>*[w="]<< R1. This proves 7 by induction. Finally, we set uM+1(x) = a(
a (R1), then H(x) = g (uMM+1(()) (77M (x)) ((>)()))
G(æ)) for all æ E K. By construction, we have H E 2NN222, therefore we have proved that the UAP holds for CNN22.
We remark that the shift cquivariance of the dynamical system (and the resulting flow map) may prompt one to consider the same equation in the quotient space with respect to shift symmetry, see Cohen & Welling (2016a). However, in the case of flow approximation, we found no new useful tools in the quotient space to analyze approximation, thus this abstraction is not adopted here.
We now give a concrete examples to show that we cannot directly deduce UAP from earlier results by quotient argument. Observe that for the non-symmetric setting, the result in Li et al. (2022a) requires that the control family FF be (restricted) affine invariant. If we directly require this affine invariance in the quotient space, then it will be reduced to scaling invariant. However, the scaling invariant property cannot induce the UAP, and the proof of this is similar to those in Section
4 PART 2 OF THEOREM T: SHARPNESS OF THE KERNEL SIZE REQUIREMENT
In this section, we prove the second part of Theorem ! Consider kernels with support & such that min E, = 1. Without loss of generality we can assume that f = 1.
We use the following example to illustrate the main intuition behind this sharpness result. More precisely, we show that the sum of two univariate function cannot approximate a bivariate function well. As an explicit example, we show that there exists eg such that
| - f(x) - s(w)ll=<((0199) 2 6p
for all choice of LP functions f and g. Suppose that for some f.g E (P 11²), |zy - f(x) (L)))=o((0o11)) we define / [0, 1/2) and pi [0, 0), P2 = [1/2, P3 =0, 10,1/2),
[1/2, 1/2]. For convenience, denote by h( y) zy. Consider the following value
M [| P1) + h(x + p4) ha(r P2) h(@ Pa)ll

---

Under review as a conference paper at ICLR 2023
Direct calculation yields that M 4 2+1
O. However, for h(z, 3) f()) + gly). it holds that ha + pı) + Max + p4) - Tax + P2) T( + ps) = 0.
By triangle inequality, M 2 0 + Σi= [I + p.) h(x + Ps)ll S 4s. Therefore, it holds that M 0, concluding the result.
For the general case of establishing the sharpness result, we mimic the example above. We introduce the following auxiliary space. For X and integer I, define æ:; the tensor in X1 = xgaax-.nn
such that [21 (62. .ia) = [ (I. .ia) Define H. as the mapping X + R such that
H [g Φ + IR: 3&6 X1 + x1, such that [((==]] = *b(x1:))-
We illustrate the function family H in the following R3x3 example. If F E H. then F should have the following form:
( (1.3))
F = g
(222),, (2.33)
(2 (3.2), (3.3) (3.3)
By the assumption on E, it is straightforward to deduce that CNN,,& res resCNN,, CODE, are all in H. It remains to show that H does not possess the shift invariant UAP. The idea follows the simple example above, by noting that in this case x now (L(1.1); 2(1,)), ((13))) now (21(2.1), (222)) 22(23)); and f(xx) + gly) is now some general permutation invariant function. We now carry out this proof.
Proof of the second part of Theorem 7 As discussed before, it suffices to show that H + IR does not satisfy UAP. Let set F(x) 11,,,,, (.)) +6 (6(2)))) (x)),, where (by) [y and K= 1)", show that there exists constant Eo 0, such that for all H E H. it holds
|F HI 2 80-
(8)
Choose two subregions of K, K2 = fo E K, Φ1: > 22
> x Fn and K₂ = fa E
K, 22: > 31: > I3: > > Tn.:). Here, say for 21 and x2 E X1. 21 > 22 means min; 21 2 max; [2) Consider the mapping т. that flips first and second rows (along first index), that
[T(a]]a = [ i + 1,2. Then T(11) = K2. By the definition of H. we have (H o T))) = H(x) for x E K1, and
[T] = [x] [T(=]]I: = [x]2.
H H + R. But F o F, which implies that
2 F [)(())) = | - Fo TT T()
< H| 11 - TllLr(k)) +I HI + - -oT (10)
= 2|| - 11 [[](
In the last equation, the last two terms are equal since 7 is measure preserving.
PART 3 OF THEOREM 1 SHARPNESS OF THE CHANNEL NUMBER REQUIREMENT
In this section, we show that the FCNN with only one channel per layer cannot satisfy the shift invariant UAP. The key to proving this part is the following observation. Suppose G E CNNI, + R. then G is continuous, piecewise linear. Moreover, by direct calculation, we obtain that there exists X, such that for a.c. K, the gradient of G' is 0 or g. The last assertion can be proved from direct calculation on the gradient of G.
Proof of the third part of Theorem 7 Based the above observation, now show that F(a:) |æo| cannot be approximated by such G in the unit ball B(O, 1). By a change of variables we rewrite
[ JESBBROL) [' [F(E) G(tg))))lll-)ddd
F((x) Pd
(11)
where |n| n2 ny.. We consider the hemisphere defined by aB 1) such that & g < 0. On this hemisphere, f(1) = F(IE) = L is increasing while g()) G(IE) decreasing in I.
To proceed, state and prove the following lemma.
8

---

Under review as a conference paper at ICLR 2023
Lemma 1. For f [a, b] IR that is increasing, we have
/ 1f gi"
/ If gl"
inf decreasing in (a.b)
inf
g constont in(o.b]
Proof. The S part is obvious, so it suffices to prove the 2 part. Given any decreasing g, set a constant 9 such that ō(1) g(ln) if f(lo) = y(ln) for some lo. and [(1) if there does not exist such a to. We can easily verify that [f(t) - g(t)l 2 (f(t) - g(t) for all t [0,
Using this lemma, we can show that
/ (5() s(1))//m-1
15(1) [(t) 12mm-
2
1/2
2 |ml inf
[s(() al'dl
eE(1/2,1] 1/2
(12)
(1 (1- 11a))t1 + (a 1/2
= ( |m/|1 inf
eE[1/2,1]
p+1
(1/4)a+1
=2 |n|+1 .2 p+1 Cp.
The last line follows from the fact that the minimization problem attains its infimum at a Therefore, (101) [F(x) G( > Caa where is the Lebesgue measure of 0B(0, 1). This implies the third part of Theorem
4'
CONCLUSION
We provided the first approximation result of deep fully convolutional neural networks with the fixed channel number and limited convolution kernel size, and quantify the minimal requirements on these to achieve universal approximation of shift invariant (or cquivariant) functions. We proved that the fully convolutional neural network with residual blocks resCNN, achieves shift invariant UAP if and only r 2 1 and L 2 2. This result does not require the specific form of the activation function. For the non-residual version,
proved that CNN, e,e has the shift invariant UAP if and only if r 2 2 and & > 2. The if part requires specifying a to be the ReLU operator. In addition, the results also hold for their corresponding equivariant versions. The proof is based on developing tools for dynamical hypothesis spaces, which has the flexibility to handle variable architectures, and obtain approximation results that highlight the power of function composition.
We conclude with some discussion on future directions. In this paper, the shift invariant UAP for CNN,,2 was established for ReLU activations. The proof relies on the special structure of ReLU: ReLU(z) x for > 0, hence we can make use of translation to replace the residual part. This construction was outlined the proof of the first part of Theorem [ It will be of interest to study the other activations, such sigmoid or tanh, can also achieve shift-invariant UAP at fixed widths and limited kernel sizes. Further, one may wish to establish explicit approximation rates in terms of depth, and identify suitable function classes that can be efficiently approximated by these invari- ance/equivariance preserving networks. Finally, one may also consider extending the current theory to handle up-sampling and down-sampling layers that commonly featured in deep architectures.
In addition to approximation error, it is very natural and useful to consider the generalization error (statistical error) in the overall analysis of a machine learning model. Compared to shallow and wide models, few generalization results in the deep-but-narron been established. While the current paper only concerns approximation theory, it is nevertheless an important future direction to establish generalization estimates.
setting (for layers greater than 3) have
REFERENCES
V. I. Arnold. Ordinary differential equations. 1973.
9

---

Under review as a conference paper at ICLR 2023
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional encoder- decoder architecture for image segmentation. IEEE transactions on pattern analysis and machine intelligence, 39(12))4411-2495 2017.
Chenglong Bao, Qianxiao Li, Cheng Tai, Lei Wu, and Xueshuang Xiang. Approximation analysis of convolutional neural networks. Submitted., 2019.
Alberto Bietti. Approximation and learning with deep convolutional models: kernel perspective. arXiv preprint arXiv:2102.1000 2021.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differ- ential equations. In Advances in neural information processing systems, pp. 6571-6583, 2018.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pp. 2990-2999. PMLR, 2016a.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In Maria Florina Balcan and Kilian Q. Weinberger (. Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2999, New York, New York, USA, 20-22 Jun 2016b. PMLR. URL https:
mir press/
748/cohencl6.oo html
Taco S Cohen and Max Welling. Steerable cnns. arXiv preprint arXiv:1612.08499 2016c.
Taco Cohen, Mario Geiger, and Maurice Weiler. general theory of equivariant enns on homo- geneous spaces. Advances in neural information processing systems, 32, 2019.
Weinan E. Proposal on Machine Learning via Dynamical Systems. Communications in Mathematics and Statistics, 5(1):1-11, 2017. ISSN 2194-6701.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimen- sionality in convolutional teacher-student scenarios. Advances in Neural Information Processing Systems, 34:9456 9467, 2021.
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse Problems, 34(1):14004, 2017. ISSN 0266-5611.
Haotian Jiang, Zhong Li, and Qianxiao Li. Approximation Theory of Convolutional Architectures for Time Series Modelling. Proceedings the 38th International Conference on Machine Learning, pp. 4961 4970. PMLR, July 2021. URL htt.::tt//////mm httttpsss//pocce...iiito ISSN: 2640-3498.
mllr press/
html
Qianxiao Li, Long Chen, Cheng Tai, and Weinan E. Maximum Principle Based Algorithms for Deep Learning. Journal Machine Learning Research, 18(1):1-29, 2018. ISSN 1532-4435.
Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning via dynamical systems: An approximation perspective. Journal of the European Mathematical Society, April 2022a. ISSN 1435-9855. doi: 10.4171/EMS/1221. URL https: wwww ems ph. org
article.
8p43--1 lix.ids= 2022-1.
Qianxiao Li, Ting Lin, and Zuowei Shen. Deep Neural Network Approximation of Invariant Func- tions through Dynamical Systems. (arXiv:2208.08707, August 2022b. doi: 10.48550/arxiv. 2208.08707. URL http:::/aaxx...or//aaaa type: article.
08707 arXiv:2208.08700 [cs, math]
Jonathan Long, Evan Shelhamer, and Trevor Darrel.. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-34400 2015.
10

---

Under review as a conference paper at ICLR 2023
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In Advances in neural information processing systems, pp. 6231-6239, 2017.
Sho Okumoto and Taiji Suzuki. Learnability of convolutional neural networks for infinite dimen- sional input via mixed and anisotropic smoothness. In International Conference on Learning Representations, 2021.
Kenta Oono and Taiji Suzuki. Approximation and non-parametric estimation of resnet-type con- volutional neural networks. In International Conference Machine Learning, pp. 4922-4931. PMLR, 2019.
Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and fully-connected networks. Proceedings of the American Mathematical Society, 148 (4):1567-1581, 2020.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter- sharing. International Conference on Machine Learning. pp. 2892-299000 PMLR, 2017.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation characterized by number of neurons. arXiv preprint arXivv1906.05497, 2019.
Lechao Xiao. Eigenspace restructuring: principle of space and frequency in neural networks. In Conference on Learning Theory, pp. 4888-4944. PMLR, 2022.
Yunfei Yang and Yang Wang. Approximation in shift-invariant spaces with deep relu neural net- works. arXiv preprint arXiv:2005.11944 2020.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference on Learning Theory, pp. 639-649, PMLR, 2018a.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. arXiv preprint 1804 10306, 2018b.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: httpppppee//ooocoedd.n...... htw.://ooccee.noo...eee.....oop. www.ips...p... cc/ pdf
Ding- Xuan Zhou Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787-794 2020.

---

Under review as a conference paper at ICLR 2023
In these appendices, provide the remaining details of the proof' of various results presented in this paper.
A UNIVERSAL APPROXIMATION PROPERTY FOR EQUIVARIANT NEURAL NETWORKS
If we remove the final layer in CNN or resCNN, then we obtain a neural network whose output data is with the same size of the input data. This is the original definition of FCNN introduced in (Long et al., 2015), primarily used for pixel-wise image tasks. Correspondingly, the symmetry property is changed to shift equivariance, instead of shift invariance. This leads the definition of the following hypothesis spaces that parallels the shift invariant counterparts in the main paper.
eqCNN, ve (fm ..... fi f1, fm E Fr,e 2 21.}
(13)
eqresCNNN, ri = {(id +fm) ....o (id +fi) f1...,,,............ E Fr.,, m. 2 1.}.
(14)
eqCODE = (f 4m) o.... (ff1,1)) " fm E F,, 12, hm R, m 2
1.).
(15)
To distinguish from functions yp: X IR, use the word "mappings" to refer functions from X
to X.
Definition 3. The mapping yp is called shift equivariant
Th((p((=)) = (TTT(a))) 2 E X, k
The mapping family X is said to have the shift equivariant UAP if
1. Each mapping in X is shift equivariant, and
2. Given any shift equivariant continuous mapping sp compact set K X, and tolerance
& > 0, there exists a mapping up E X such that
|/b (1l S.
Then, the analogous result with respect to equivariant approximation is stated follows.
Theorem 3. We have the following results.
1. For the fully convolutional neural network with residual blocks, it holds that eqresCNN, r, possesses the shift equivariant UAP for r 2 1, and 2 2. For non- residual versions, eqCNN, possesses the shift equivariant UAP for > 2 and i > 2.
2. The kernel size 2 is optimal in the following sense: for & with min e 1, then neither cqresCNN, x..8. + nor cqCNN x. + IR possesses eq-UAP.
3. The number of channel for non-residual fully convolutional neural network is optimal, in the sense that the mapping family eqCNN R does not possess the shift equivariant UAP.
To prove Theorem 3 start with the following proposition, which links the universal approxima- tion property of invariant function family and that of an equivariant mapping family. A version of this proved in Li et al. (202b)) in rather abstract setting for general transitive groups. We provide a more explicit proof Appendix B.3 in the specific case where we are only concerned with shift operator Ta.
Proposition (Equivariant UAP is Sufficient). Suppose g X + R is Lipschitz, permutation invariant, and g(X) = R. If mapping family A possesses the shift equivariant UAP, then B {g o E A} possesses the shift invariant UAP.
The corollary of this proposition is that, using the first part of Theorem 3 can derive the first part of Theorem [ while using the second and third part of Theorem we can prove the second and third part of Theorem
Finally, it remains to show the following theorem, which is an equivariant version of Theorem 2 As in the proof procedure described in Appendix B.4 all other results will be reduced this theorem.
12

---

Under review as a conference paper at ICLR 2023
Theorem 4. The mapping family 1 satisfies the shift equivariant UAP.
Proof of Theorem Using the fact o f E eqCODE, = CODE,, Theorem 4 and
Proposition 2
Proof of Theorem 3
The first statement follows from Theorem 4 and Proposition second statement is false, that is, eqCNN.c. possesses eq- eq-UAP. Then, since
| Suppose the
o f: ff EecCNNo, C R,
from Proposition we can deduce that CNN has shift invariant UAP, contradicting to Theo- rem I
The remaining sharpness result also can be proved in similar manner.
Thus, to deduce Theorem it remains to prove Theorem 4 and Proposition These proofs
presented in Appendices B.4 and B.3 respectively
B TECHNICAL DETAILS
In this section, we provide detailed proofs of results that were quoted the main paper and the previous section in the appendix. The overall plan of the proof is the shown in the following diagram, including the dependency of each propositions, theorems, and their proofs.
Theorem (Sec.
Theorem 3 (App. A)
Part
First Part
Second Part
Second Part
Proposition (App.
Third Part
Third Part
Proof: Section
Proof. Appendix B.3
Section Proposition
Proof:
Proposilion 1 (Sec. 3)
Theorem 2 (Sec. 3)
Propositio
Theorem 4 (App. A)
Proof: Appendix B.2
Proposition (Appendix 4)
Proposition 4 (Appendix B.
Point Matching Property (Appendix B.
Appendix
Lemma (Appendix B.1)
Appendix
Proof: Appendix B.5
Figure 2: The directed acyclic graph represents the dependency of the result and the section layout.
13

---

Under review as a conference paper at ICLR 2023
B.1 CLOSURE OF A MAPPING FAMILY
We begin with some elementary properties of compositional hypothesis spaces. For given bi- Lipschitz mapping family 9, consider closure in the following sense
clo(g) == {4 E (), for any compact K C > 0,
(16)
Edpb E 99 such that|| - 40 (l))(() S
Then, have the following lemma. Lemma 2. IfG is closed under composition, then so is clo(G).
Proof. Take o B E clo(g). by definition it suffices to show that a B E clo(g). For given compact
K X and > 0, there exists 3 such that
|
B (F)) Se'=
2Lip (ax
Also, there exists a' E G such that
||o' all()(((K)) S E Lip 3'
Then
|| o og' - o S|la' o B a + ||a B' a 3 LF(K)
Lip (a))²
(17)
Se.
Since a' o 3' E G, this shows a o B E clo(g).
Lemma 3. If (lo possesses shift equivariant UAP, then so does
Proof. By definition, for given shift equivariant function s,, compact set K X, tolerance 0, there exists E clo(g) such that
||<0 (PllLo<K) S e.
From the definition of clo(G), there exists 402 E 9 such that
|| (P2)l S.
Hence,
114 (2ller(K) 1 28,
which concludes the result.
B.2 PROOF OF PROPOSITION
We first prove that + Φ(f, T) can be approximated by such $ (id (id+(T/n)ff"* For given
t 0, since
()(f,t)(x: - x-(f(x)) S ((o(f,))())) f(x)lds
< / L( s)(x) - x
(18)
L12
2 f(()) + S/ L|Ø(f, s)(x)) -ff(x)lds.
14

---

Under review as a conference paper at ICLR 2023
Therefore, by Gronwall's inequality, we obtain,
( - --- - sc(t++ S C(s)clit-odds
LE
Lt3
(19)
2 --15(= 1f(xa <41ʃ
fort S m 1), where C(t) / f(x)].
This local estimate be improved obtain the desired approximation result. For given T, t == T/n. Define 4h ( ((fft)) 1)) and Th (id (1)()))))) Then, holds that
(x) - ((tx) 2 (xx क (x)) + ( "- (x))
x (x))
(20)
<Lf (x) + Lip 3/ (z)1
Suppose that M [0P] [a)) since Lip क 1
+ (<) (+)) S LM (1 + (L] "--1(1)) (x) - -x--1(x)))
(21)
By discrete Gronwall's incquality, it holds that
(1 tL)
(1 (1+ - LMP S TTMMt.
(22)
The above estimates implies that, define
{(id fmm o... (id +tifi) fI, fm E F
then
Φ(f.t) clo(g).
By Lemma
2
we conclude the result.
B.3 PROOF OF PROPOSITION 2
Proof of Proposition enlarge K.
Without loss of generality, we assume that K [-a, af",, otherwise we can
Define
K1 = E K [x]1
[x), Vi * 1.}
Then, is easy to check that
K = U(TK))
up to measure set. Define e any s there exists u such that
(1+Lip gj* by results in Li et al. 2002a Theorem 3.8), for
F go u u|] S
(23)
Note that u here is not necessarily equivariant, otherwise we are done. Now we attempt find by some kind of equivariantization on as explained below. Since u is in LP, we consider a compact O K2 such that [u|l tet (0) I e'. Take smooth truncation function X E C (Rd)), whose value in [0, 1], such that xlo and x|æę 0. Then á Xu smoothed and truncated version of u.
For TiK1 with index k, define
f(x) = (T((T=((<))
Since different TaK disjoint, the value of f is unique in TT We set f(x) 0 in the complement U2 T The truncation function X ensures that f vanishes on the boundary of Q therefore f is continuous, and direct verification shows that f is shift equivariant.
15

---

Under review as a conference paper at ICLR 2023
It then suffices estimate || g flr, since both F and g equivariant, it is natural and helpful to restrict our estimation on K1. since
|| g fll ( n || 9 fl(eF(K))-
(24)
To estimate the error K1, we first estimate the enror ||u f(lea(k))) Since and flx, ú coincide on O, we have
u (o-ffll((.)))) = 1lue 1 ((llūl((o(.))))
(25)
1 <1 = =
The inequality follows from the fact that takes value in [0, 1]. Since is Lipschitz, we have lgg o u go fllLF(K,) S Lip ge', yielding that P| go fll S (1 Lip g)s'. We finally have |F go fl) I (1+ Lip m
B.4 THE PROOF OF THEOREM
In this section prove the UAP of eqCODE Here, we relax the constraint that ReLU. We make the following assumption on a, which is called "well function" in Li et al. (2022a).
Definition 4. We say Lipschitz function h R bounded (closed) interval.
well function if {x R h(z) 0} is
In this section, we assume that there exists a well function in the closure of span (wr (w: +b), v, w. b R]. The commonly used activation functions meet this assumption, including ReLU, Sigmoid and Tanh, see Li et al. (2022a). For a given continuous function u - R. define the by [u (x)]; = u([z])).
coordinate zooming function u
We say point is stabilizer if and only if there exists non-trivial l 0, such that
T æ.
We say point set X {xx x ..... x²) shift distinct, if for some é1, ig, & with
The (x(* x²
then we must have i = is and & O. Notice that if point set X is shift distinct, then for any
member æ E X, the only so that (x)) æ is k = O. This is implied by the definition shift distinctness. The basic approximation framework is based the following two properties.
Proposition 3 (Basic Framework). Given a family A of mappings X + X. Suppose A is closed under composition. If satisfies the following two conditions:
I.Coordinate zooming property) For any continuous function u, the mapping u is in A.
2. (Point matching property) For given shift distinct point set x...... "M target point set y' ...... "y and a stabilizer point set s', s,,,... ,N, a tolerance > 0, there exists mapping &p E A such that lppxx") - 2 S
and
(p(8)) 51. 1
Then, A possesses the shift equivariant UAP.
Note that for the point matching property is to say, we can use mappings in & to move each æf y². while keeping stabilizer set stay around the original point. We now use this proposition to prove Theorem consider the closure in the UAP sense, that is,
A = { for all compact C X > 0, there exists &b COCEDE
(26)
||yp wb (ZP(K) $ c.}
16

---

Under review as a conference paper at ICLR 2023
Proposition 4. The following results hold for the mapping family A.
1. A is closed under composition.
2. Given w X supp w S and E RR then the flow map @(h(w + +b),t) E A
3. A satisfies the coordinate zooming property.
4. If A possesses shift equivariant UAP, then does eqCODE1,2
Suppose now the point matching property holds for A, we then prove the main theorem (Theorem)
Proof of Theorem By the last part of Proposition it suffices to show that A possesses shift equivariant UAP. By the third part (and the first part), we know that if A has the point matching property, then A has shift equivariant UAP, which concludes the result.
From the proof, we know that: Once the point matching property is proved, Theorem then proved. The proof of the point matching property is the most technical part in this paper. We first give sketch of the proof.
Sketch of the proof of the point matching property. In this sketch, we only consider the case when there are no stabilizers, i.e. when N
Step 1. We first show that if A has the following point reordering property, then A has the point matching property.
For any shift distinct point i, can find mapping &p A such that
(x((=)));
(<p(x*) }]ar
j < or j= but j. Here the partial order the lexicographic order. For brevity, we say in this case that (a(r)) ) is ordered.
Step 2. To begin with, we first prove that there exists mapping 3 E A. such that
[a<<"));>>(a)) [[(()))
for # 1 and any indices i, i'
Step 3. Set 2 = B(y²). Now we are ready for an induction argument. Suppose for 22, ... we have mapping 2b E A to fulfill the point reordering property. We modify it to the mapping 20 2b t A, such that it satisfies the following conditions
(x²"). ... (> are ordered.
[+>(2)) ) > [xb(2))) Ir for j + 1, and indices i, i'.
Step 4. Finally, we modify & to get 4o such that sp(x") is ordered. Till now, we prove the point reordering property for A.
The full proof of Theorem is put in Appendix B.7
B.5 PROOF OF PROPOSITION 3
Proof of Proposition 3 Without loss of generality, we can suppose that K = [-a, a)m.. Otherwise, expand K sufficiently large hypercube.
17

---

Under review as a conference paper at ICLR 2023
Step 1. Given scale 5 0, consider the grid 6z with size 6. Let q 2 be tensor with all coordinates being integers, and Xq be the indicator of the cube
4.8 = { x [a) E (0 (1q)s + 1)6}}
(27)
Since yp in IP(,), by standard approximation theory &p can be approximated by equivariant piecewise constant (and shift equivariant) functions
(o(x))
Σ
(a)a(
(28)
q G.scK
where
y/ X1D
(d(x)d
(29)
is the local average value of in 9.5. Then, we have
|| (Pll S (K()))(())) + as 5 > 0, where wip is the modulus of continuity (restricted to the region K), i.e.,
(30)
(ip(0)
sup
[(((x) (p())
(31)
vo
for x and y in K and X(K) is the Lebesgue measure of K.
Step Let qō be vertex of 4..6 Define I the maximal subset of To {q 9ó K} such that {qó q E I} is shift distinct. By the maximal property, and the definition of shift distinctness, for each q To, only two situations can happen.
1. There exists a shift operator To and q' E I, such that Taq' q.
2. q itself is stabilizer, that is, there exists a shift operator To with k of 0 such that T&q q-
By the construction of yg it holds that
Tky
VTa99*
Given 0, by the point matching property, we can find f E such that
For q E To that is not stabilizer, (f(g0) yy E.
*
For q E To that is stabilizer, [f())) <
For (0, 1), define the shrunken cube
q.6 == fo X [æ];
[[g],d, ([g]i + a)0}},
(32)
and define K = LD, cK 0 aa which is a subset of K. Given | > 0, we now use the coordinate zooming property of A find a such that
ullih, (i + ah))) C [ih, (i + 26) for E (i::8=1 ni E
(33)
n To do this, we construct piecewise linear function u such that
ul (1(30,(++)) = 5,
(34)
2n
by setting
8
u (1
(i- -i-aii))/(1 a)))/(1 +
(35)
2n
explicitly, and select 8 < 3n
By the coordinate zooming property, @ is in A.
Therefore, have
18

---

Under review as a conference paper at ICLR 2023
[f())(x)) yql - for a E D q.8
(36)
q is not stabilizer, and
If(u (a)) S 1 + for x E 0 9.60
(37)
if q is stabilizer.
These estimates (36) and 37 will be useful in the final step.
Step 3. We are ready to estimate the error ||5p - f o u [(((
The estimation split into three parts.
K
K
K
U
9,8
not stabilizer
(38)
K2
U stabilizer
9.6
Notice that Ka
-00g 9.6*
For Ky. from 36
the end of Step 2, we have |I a u - -Pollo S 2E, and thus
I の <PolLe(KY)) I 2=(A(K S 2c{X(
(39)
For KG. note that if q is stabilizer, then all points in 4g,5 will be close hyperplane
Fij: = {o E X [x]] = [زري}]
for some distinet i,j, the distance from those points to T will be smaller than v/n.ō. Therefore, the Lebesgue measure of Kž C K2 will be smaller than that of all points whose distance to the union of hyperplanes j less than vnd, which is O6)). Thus, have
If 8 (ollee<KG) S (1
((Pollc(k))0(5))
(40)
S (1 + e (pllcck))O(B)
The last line holds since [| S ||<|locc) by construction.
For K) \. Ka we have
Iff o o - <olloo((((()))
S (llfflcc + l|+llo()) A(K Kaji/v (Ifflcc + -
(41)
We first choose 5 sufficiently small such that the right hand side of 40 is not greater than then choose a such that 1 - is sufficiently small, and ([fllc()) + || (p)) conclude the result since f @ E A.
(1 ad) Ss. The we
B.6 PROOF PROPOSITION
The first part and the last part comes from Lemma and respectively.
Part We show that for f.g E F1,2, then
o(f + ffftgT71 A.
From Proposition] I we know that for compact K C X and tolerance > O. Then for sufficiently large n,, set / = T/n, we then have
Φff g. l)l S. (idd +if + 1g)"
19

---

Under review as a conference paper at ICLR 2023
We now estimate the enror between (id +tf + fg)" and (tf)+tf) o (id tg)]".
Since
+td+ o (id +tg) (id +tg)(a) + +f (g(x)))
we then have
(id +ff) o (id (z)) - (id +f (g)(=)) & PLip f f(g(z))
Similar as 20 a telescoping decomposition yields
(fid+ff) (id +tg)]" (id (t)+
< Lip flg (g) (g)"-
(1 + 2tL 2t (id +tg)] [tgg)= (a) (id (id+tf (g) --gggggg (x>))
Since from 20
[id +if + (0)))((())) Φf + g. (n 1)))()) S Mle
(42)
then holds that
[[(id +tf) (id +xg) - (id +tf + tg)
S(M + M)
+ (1 / (id +(g))" +ff (g)"" (xr)
(43)
Using the discrete Gronwall's inequality again, have
[[(id +tf) (id (x)) (id +tf + tz)) - 2TL
(44)
Hence, for sufficiently large n, we can show that
[[(id +If) (id +(g)]"
(g) Se.
(45)
Finally, by the same estimates in Proposition | we have
[[[ +tf) o (id + tg)]" (o(f, t) Φlg " [L) S
for sufficiently large n.
Therefore, we prove that @ff + g, T) E clo(A)) Using similar approach, we can show that f is linear combination of mappings in F1,2, then o(f,T) E clo(AA).
Step 3. Now, for a certain well function h, we have proved that
Φ(h w * 61),t) E A.
(46)
Choose w such that (1.1..... .1) = w but = 0 for other multi-indices. Then the dynamical system decoupled, in the sense that each coordinate evolves the one-dimensional dynamical system
vh(ws b)
(47)
for some v, w. b E R.
Set
K. = [wh(w +b), U, w. E lF
and define
= ( (m) .... (1), Jm Im- Si E H, 1mm21 1.)
For the following proof, suppose that II = {ar R h(x) 0}. Note that both IC and G are function families consisting of function from to R. The third part of the result comes from the following lemma.
Lemma 4. For any increasing continuous function R R, have E clo(g).
20

---

Under review as a conference paper at ICLR 2023
Proof. Given interval K R, and tolerance
find a 9 such that
||u u (P) S
We choose < 22 < ... < En. with xi and Hn being two endpoints of the interval K. Notice that we can find ū E 9 such that ū(x;)) u(x,), 1,2, ,M, then by the monotonicity of both and ú, it holds that
| k) S w(K,)), h).
where h max; 2i+1 - 2i, and w/ (K the oscillation of u in the interval 1. Then, we obtain
| u (K)) w(K, k)]
which implies the lemma.
We prove by induction that there exists inn G, such that (x)))) u(z;), 1.2, ,
(48)
Set Po = id. Choose suitable e and b R such that
(m))), ... (a(xn) wll +
but
Pn (n(2nt1), .. Ppn(x wI + b.
Then, the dynamics
= v +b)
will keep all i 1ovi=1,, 1,,, n fixed, but will move Pn (T to u(xx41) for certain +1 and
certain >> 0. Therefore, we found Pn+1 E G which satisfies 488).
B.7 COMPLETE PROOF OF THEOREM 4
In this section, we complete the proof of Theorem As discussed in the sketch of proof (Sec- tion B.4), first consider the case when there stabilizers be dealt with.
Step 1. We first show that if A has the following point reordering property, then A has the point matching property.
For any shift distinct point set wi 1,2, M, can find mapping &o A such that
(x<(x)) 14p(ar")) })r
j or = j but x j. Here the partial order x is the lexicographical order. For brevity, we say this case yp(x) (xx) ordered.
Without loss of generality can assume that y' is also shift distinct. Suppose there exist &a. and Sy E A such that & (x*), = 1, 1,2,3 .M is ordered, and (yr)) 1,2, ... M is ordered.
Then we can find continuous mapping such that
(((p)((x)) = u((s )1s)
holds for j 2, M and all the indices i. Therefore, the mapping by a 4o is then constructed to satisfy the point matching property.
Step To begin with, we first prove that there exists mapping 33 E A, such that [o<(>))] )} > [<<('))]
for j > and any indices i, i'. We first show that can perturb the point set x' 1,2, M such that all the coordinate [x']e,] = 1,2, ... M, i I n, are different. In what follows, we say that in this case a perturbed.
The perturbation argument is based on the following minimal argument. For a E A, consider the following quantity:
F((:) ((i.j, :1 or H (x((2))) )} [[a('"'))) )]a
21

---

Under review as a conference paper at ICLR 2023
Suppose minimizes this quantity, it suffices to show that E(a) 0. Otherwise, consider pair J) and (I' sch that (I + J') but
[a<(<>)) )r (ax(x )rr-
Since (xx") and (xx")) must be shift distinct, no matter whether J and J' are identical, we can deduce that there exists and e, where (0, 0, ,,, ,,,... ,0), such that
(a(<"))11k 1a(a" 1
(49)
but
(e(x)))(4++ * |a(x ) blr+bte. So without loss generality, we may assume that 0, and 01,0,0, 0).
(50)
Consider the following dynamics
d
|2| |=|= f(z) ((z]ite +).
di
Here the constant is chosen to ensure that the
(((o(()))) Itte + b) 0 + o ((a((> 11
Then for sufficiently small t 0, the inequality
F(((f,t) R oa) F((())
leads to contradiction of minimality. Therefore, there exists E A such that a(xx), 1,2,-.. M is perturbed.
So far, assume that x' = 1,2, ... .,, itself perturbed, since can apply perturbation a to achieve otherwise.
Consider the following quantity:
K(a) ((i, : 1 [[(o(( 2 [<x(x=)))+)
We choose an a E AA to minimize this quantity in A subject to c<xx)) ) is perturbed. Now it suffices prove that K ((aa) 0. Suppose not, then there exists J, I') such that
w = [a<(
)]r [ax(x')) )rr-
the smallest one among choice that makes the above value non-negative, Clearly, no other [axx)) ) is inside (c<==)))x,,(td) [a(x)))()))) Since have assumed ((xx). 1,2, M is per- turbed, then w * O.
We define continuous function R + I, such that
v((a(=))) (((a(())) S μ..
For other pairs, (i.j. # J, it holds that
(=(()()))) o( ((a((2)) }]e) 3c.
Here and μ and I = I' + (1, ... 0). Consider the dynamics (for short, we only write the equations for the coordinates we are concerned with)
parameters whose values will be determined later. Set I = I (1,0 .0)
dt [2) (o((2),, + b),
d
di [>]r vo[[2); b).
We choose certain and E IR such that
(ax((<( }]r + =0
22

---

Under review as a conference paper at ICLR 2023
and
va((((<')) + =1
From classical ODE theory, the dynamics will move each [ar(x')]; [a(t)] such that
- [a(t)]}k] S Ci(e"Cs
for some constants C1, C2 depending only on e. We choose a sufficiently small i such that the right hand side less than Therefore, we always have
vo((a(t))rx+ +))= =0
and
vo vo((a(t))rr+b +b) 8
min
vo(().
rE[1+2,1+3e]
Note that this 5 only depends on E. Then we can choose = min ( t6, c²), and therefore we at least have
[a(t))r (a(t)"Ir,
while the other order are preserved since & is now much larger than μ. This contradicts with the minimal choice of a. Hence, we conclude the result.
Step 3. Set 2 = (3y'). Now we are ready to proceed with induction. Suppose for "².... M have mapping & E A to fulfill the point reordering property. We modify it to the mapping ab 1b a E A. such that it satisfies the following conditions
(b²)), .... 3) are ordered. [2b[(2)) ) (x)())))s for j * 1, and indices i, d'.
Since restricting db in the line R1, we can obtain a continuous increasing bijection from R1 R1. We can find > 0, such that
a max 3#1
and
r(al) max (xxx))/22)) + 2T.p sb.
Define u such that fixes all [2'), for j * 1 and all indices i, but sends [>*] to the interval [a 1,a 1]. We consider db 2/ t E A. which satisfies the following conditions
(522), ... x) are ordered.
[x)())) > (xb())) e for j * 1, and indices i, i'
Step 4. Set p¹ ()) Similarly, we consider the following quantity. For A such that
1. y(??), ... (M( is ordered.
2. (x(p)) }}; > (n(p))) |r for j * and indices i'.
We define the following quantity
L(>) (i,,') : <r'")r(("))) < (r(x))ee }e
We claim that this quantity is zero. Suppose not, then we can find a pair (I, I') such that
I I
but
hr [>(x*))
minimal among all the choices that make this value positive. One verify the following result, that there must be no other indices such that
(r (r(=)))r,
23

---

Under review as a conference paper at ICLR 2023
since in this case either I k k I' should be satisfied, which contradicts with the choice of and P. Therefore, there exists a continuous function v such that
"(>(2)))) 2 )bn)))>>>>>)) 14
and
((>(<>))) - <(>(<< ) E.
From a similar argument as in Step 2, we can construct a new y satisfying the condition but with minimal L(7). Therefore, we conclude the result.
Dealing with Stabilizers We conclude the proof with the situation where there are stabilizers. We prove that there exists A such that
[<x")] [((=")) Dl
(51)
for all possible choice (i.)). (F',))) In such Ç exists, we can proceed, as we did in Step 3, to find a yp E A, such that
1.
(g<(x)) > (sp(x") )3s
j < or = but x.j.
2.
[(p(x))|; )); (x((x") )]
for all possible choice of (i.j), (1),
We first show that, with this point reordering property with stabilizers, matching property. Compared to what we did in Step 1, suffices to additionally assign the value o o',0²² N as the target of s', where each coordinate of p is chosen be S 1.
prove the point
Suppose for target y'..... M and ő = 0, such Py E A can be found. We choose o , around the value Py (o))), such that
Jo' (o(ol Ss,
and moreover we can assign v these value such that v((>'))) = [o']:. Hence, the requirement of point matching property be fulfilled if we choose < (Lip 4p )-
Now we prove the existence of Ç. Consider the following quantity,
H() := {(i, i', "', [C(x)), S [c(s [[s And we choose Ç E A to minimize this quantity. We only need to show that H(C) = 0. Otherwise, we can prove that we can construct a new Ç A with a lower value of H()).
This construction is similar to what we did in Step 2, in that we only need to find a such pair (I, 1', such that
IS(s )r 2 [((x"))r
(52)
and there are no other coordinates between these two value, but with an e = (0, ... ..... such
that (5(x)))x+e # [Ç(s")) )[re
We assert that such pairs can be found. Suppose this assertion does not hold. Since we assume that H(() * O, which immediately implies that there exists at least one pair J and J', such that for some multi-indices I and I', (52h holds. We choose such (I, J, I', J') to minimize the quantity
w w= )r [C )r If this quantity w does not equal to zero, then clearly there is no other coordinates between these two values. But since the assertion does not hold, we can derive that
[<(x))) ) re [)
Therefore, the quantity w should be zero. Thus, the problem reduces the case when w 0.
In this case, we start from a pair [x = | we can show that for all e (0, ... 10,,...,,..... ...,,,,000000 0),
have
[x:" Itte = [s Ir+e-
Repeating this procedure, we can know that the above identity holds for all choice of e. Therefore, there exists a shift operator Th such that Txx s which also leads to a contradiction, since implies that and is stabilizer.
24


Reviews:
[{"review_id": "ijnIumF0_yU", "reviewer": "Reviewer_RUpT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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:\n1. Proving them for small width networks (with arbitrary depth). For example, the work of Lu et al. 2017.\n2. Proving them for invariant (equivariant) functions and for corresponding  invariant (equivariant) networks. For example, the work of Yarotsky 2018.\n\nThis 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.\n\n\n", "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.\n\nDue 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. ", "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.\n\n\n\nOther comments:\n1. ‘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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SjcQvtDrTo", "reviewer": "Reviewer_iJgd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "Interesting result, but not useful enough by itself.", "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.\n\nWhile 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.\n\nHere are some suggestions on what could strengthen the paper:\n- 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?\n\n- 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?\n\n- 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)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0c2vBkmmJ8", "reviewer": "Reviewer_gqo7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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 \n- the number of channels is at least 2. \n- the kernel size is at least 2 (in each coordinates)\n- the network is sufficiently deep (essentially, infinitely many of layers)   \n\nThe 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.) ", "summary_of_the_review": "update\n\nThanks a lot for the detailed and insightful reply. I will keep my score. \n\n------\n\nAlthough 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.  ", "strength_and_weaknesses": "# Strength \n\n- The overall mathematical clarity of the paper is far above typical ML conference papers. \n- Both the results and proofs are non-trivial. \n\n# Weaknesses: \n- 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). \n- 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. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject