Theoretical Analysis of the Inductive Biases in Deep Convolutional Networks
Authors: Zihao Wang
Lei Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: Convolutional neural network
Inductive bias
Universality
Sparse function
Equivariance group
TL;DR: We theoretically analyzes the inductive biases of deep CNNs, including downsampling, multi-channeling, weight sharing, and locality, showing CNNs' efficiency in learning sparse functions and their separation with LCNs and FCNs.

Abstract: In this paper, we provide a theoretical analysis of the inductive biases in convolutional neural networks (CNNs). We start by examining the universality of CNNs, i.e., the ability to approximate any continuous functions.  We prove that a depth of $\mathcal{O}(\log d)$ suffices for deep CNNs to achieve this universality, where $d$ in the input dimension.  Additionally, we establish  that learning sparse functions with  CNNs requires only $\widetilde{\mathcal{O}}(\log^2d)$ samples, indicating that deep CNNs can efficiently capture {\em long-range} sparse correlations. These results are made possible through a novel combination of the multichanneling and downsampling when increasing the network depth. 

We also delve into the distinct roles  of weight sharing and locality in CNNs. To this end, we compare the performance of CNNs, locally-connected networks (LCNs), and fully-connected networks (FCNs) on a simple regression task, where LCNs can be viewed as CNNs without weight sharing. On the one hand,  we  prove that LCNs require ${\Omega}(d)$ samples while CNNs need only $\widetilde{\mathcal{O}}(\log^2d)$ samples,  highlighting the  critical role of weight sharing. On the other hand, we prove that FCNs require $\Omega(d^2)$ samples, whereas LCNs need only $\widetilde{\mathcal{O}}(d)$ samples,  underscoring the importance  of locality. These provable separations quantify the difference between the two biases, and the major observation behind our proof is that weight sharing and locality break different symmetries in the learning process.

Theoretical Analysis of Inductive Biases in Deep Convolutional Networks
Zihao Wang
Lei Wu Peking University leiwu@math, pku.edu.
Peking University
zihaowang@stu. pku. edu. on
edu. en
Abstract
this paper, we provide a theoretical analysis of the inductive biases in convolu- tional neural networks (CNNs). We start by examining the universality of CNNs, i.e., the ability to approximate any continuous functions. We prove that a depth of Oloo d) suffices for deep CNNs to achieve this universality, where in the input dimension. Additionally, we establish that learning sparse functions with CNNs requires only (log" d) samples, indicating that deep CNNs can efficiently capture range sparse correlations. These results are made possible through a novel combination of the multichanneling and downsampling when increasing the network depth. We also delve into the distinct roles of weight sharing and locality in CNNs. To this end, we compare the performance of CNNs, locally-connected networks (LCNs), and fully connece networks (FCNs) on a simple regression task, where LCNs can be viewed as CNNs without weight sharing. On the one hand, prove that LCNs require ((d) samples while CNNs need only Olog² d) samples, highlighting the critical role of weight sharing. On the other hand, we prove that FCNs require (2d2) samples, whereas LCNs need only (d) samples, underscoring the importance locality. These provable separations quantify the difference between the two biases, and the major observation behind our proof is that weight sharing and locality break different symmetries in the learning process.
Introduction
Convolutional neural networks (CNNs) (Fukushima, 1988; LeCun al., 1998) are fundamental
model in deep learning, known for their exceptional performance in many tasks. In particular, CNNs consistently outperform the fully-connected neural network (FCN) counterparts in vision-related tasks (Krizhevsky et al., 2012; He et al., 2016; Huang et al., 2017). Uncovering the underlying mechanism behind the success of CNNs is thus of paramount importance in deep learning.
Zhou (2020a;b); Feng et al. (2022); He et al. (2022) studied the approximation capabilities of CNNs for target functions in spaces such as continuous functions and Sobolev spaces. Although these results are important, they cannot explain why CNNs perform better than FCNs. The primary reason for this limitation is that these works did not take into account the specific structures of CNNs, including multichanneling. downsampling. weight sharing, and locality. The locality refers to the use of small filters, e.g., filter sizes be small 3 in popular VGG nets (Simonyan and Zisserman, 2014) 4) and ResNets (He et al., 2016). Comprehending the inductive biases of these architecture choices is critical understand the exceptional performance of CNNs.
Li et al. (2020) designed simple classification task to demonstrate the superiority of CNNs over FCNs. The authors prove that for this task, FCNs need 2(d)) samples while CNNs need only ((1) samples, thereby providing theoretical support for the superiority of using convolutions. However, this study neither examined the individual impact of weight sharing and locality considered the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

inductive biases of multichanneling and downsampling. Additionally, the analysis was limited to shallow CNNs and did not examine the interaction between these structures and network depth.
1.1 Our Results
In this work, we conduct systematic analysis of the inductive biases associated with the specific structures of CNNs. Our main contributions are summarized as follows.
Universality. We establish the universality of deep CNNs with depth of (log d). This is in contrast to existing works (Zhou, 2020a;b; He et al., 2022), where the universality requires a depth of at least (d).. The key to our improvement is an effective leveraging of the inductive biases of multichanneling and downsampling:
Downsampling amplifies the size of the receptive field exponentially, thus explaining the need for logarithmic depth. Furthermore, we prove that if downsampling not used, CNNs require depth of at least (dd), demonstrating the cruciality of downsampling.
Multichanneling serves as a mechanism for storing extracted information. By increasing the number of channels whenever the spatial dimension reduced by downsampling, we ensure that no information is lost. This combination of multichanneling and downsampling is widely employed in practical CNNs, ranging from classical LeNet (LeCun et al., 1998) to modern VGG nets (Simonyan and Zisserman, 2014) and ResNets (He et al., 2016).
It is worth mentioning that while studies like Poggio al. (2017) and Cagnetta al. (2022) have examined similar CNN architectures with Olog d) depth, they did not explicitly establish universality as our work does. Specifically, Cagnetta et al. (2022) focused on the kernel associated with deep CNNs having infinitely many channels. In retrospect, one could potentially show that the deep- deep-CNN kernel is universal by verifying that kernel has no zero eigenvalues.
Learning sparse functions. A function f TRd + IR is said to be sparse if it only depends on few coordinates of the input, e.g., [(x == , 3aa for some g R22 - R. We prove that learning sparse functions using CNNs requires only (log" d) samples, which is nearly optimal as the information-theoreti lower bound of learning such functions is Mllog d) (Han and Yuan, 2020).
This result surprising because has been widely believed that CNNs struggle to capture long-ram long-range correlations. However, our findings suggest that CNNs can efficiently learn long-range sparse ones, which is a valuable attribute for many applications.
In addition, is important to note that the near-optimal sample complexity of learning sparse functions using CNNs is achieved with only O(log d) depth and O log d) total parameters, where k is the number of critical coordinates in sparse functions. A lower bound is established to demonstrate the optimality of the depth requirement. The ability of CNNs to select any k coordinate with only Ok22 log d) total parameters is remarkable, especially considering that even in the linear case, LASSO (Tibshirani, 1996) requires ((d) parameters. It is the synergy of increased depth, weight sharing, and multichanneling that gives CNNs this exceptional capability.
Disentangling the weight sharing and locality. We next study the inductive biases of locality and weight sharing by comparing the performance of CNNs, LCNs, and FCNs on a synthetic regression task. This allows to separate the effects of weight sharing and locality.
CNNs vs. LCNs. We prove that CNNs requires only Öllog d) samples to learn, while LCNs trained by SGD or Adam with standard initialization need ((d) samples. This provides separation between CNNs and LCNs and demonstrates the crucial role of weight sharing.
LCNss vs. FCNs. We prove that LCNs requires only Ö(d) samples to learn, while FCNs trained by SGD with Gaussian initialization need ((d?) samples. This provably separates LCNs from FCNs and demonstrates the benefit of locality.
The difference in sample complexity can be attributed to the different symmetries encoded in the architecture biases. For instance, stochastic gradient descent (SGD) exhibits different symmetries for these models: lack of equivariance for CNNs, local permutation equivariance for L.NSs, and global orthogonal equivariance for FCNs. The size of the equivariance groups determines the

---

minimax sample complexity and distinguishes between different architectures. Similar ideas have been previously explored in Li et al. (2020); Xiao and Pennington (2022) to understand CNNs; but these works did not differentiate the roles of weight sharing and locality. For a detailed comparison with these works, see the related work section Appendix
Technical contribution. The lower bounds for LCNs and FCNs are established using Fano's method from minimax theory (Wainwright, 2019, Section 15). However, different from the traditional statistical setup where the estimator is deterministic, the estimators produced by stochastic optimizers are random. To address this issue, we develop variant of Fano's 's method for random estimators, which might be of independent interest. Further details can be found in Appendix B.3.
Related work.
We refer to Appendix A for a detailed comparison with other related works.
1.2 Notations
We use poly(21,...... Zp) to denote a quantity that depends on 21.....;Zp polynomially. We use X S Y to denote X < CY for some absolute constant C and X 2 Y is defined analogously. We also use the standard big-O notations: (c)), O(-) and ((-)). addition, we use Ô and Q hide higher-order terms, e.g., O(log d) (log log d)²) = Olog d) and Od = (d). J In addition, we
use Gon (d) to denote the orthogonal group in dimension d:
Gon (d) = (Q E Radd QQQ Q Id).
Let P((2) be the set of probability distributions over Ω and M(S2) be the set of random vari-
ables taking values in Q. Given two functions f.g over X' and {xi]i= let pa =
V [f())) - g(x,) Let Sd-1 = {o E Id : || = 1), = {a : I/r E 1d-1). Let A = min(a, b). [k]] (1,2,...., for k E N, and [a,
+a,a+1,,... b) for b, E N and b a. For vector v. denote by ||v||p =- ( |u,|p)//P the l" norm. For matrix A, let || and || p be the spectral norm and Frobenius norm, respectively. Moreover, denote by A and A the i-th row and j-th column, respectively, and similar notations are also defined for tensors. Given
I = (d1, i2...., . ). let X2 (I.,..... Liz ). We use to denote both the activation function and
standard deviation of label noise. To avoid ambiguity, we shall use a(-) and a to distinguish them. When applying (-) to a vector/matrix/tensoo it should be understood in an element-wis wise manner.
2 Preliminaries
We consider the standard setup of supervised learning. Let X Rdd and y R be the input and output domain, respectively. We are given the training set S, {(I;, y/) B with yi sid (x;) + E,, ~ P. and &: ~ function, respectively. We assume log, d E N+ for simplicity. Let h X' θ R be our parametric model with θ = IRP, where p denotes the number of parameters; we often write he = h(=;;) 0) for short. Our task
sid o"), Here P and h² denote the input distribution and target
recover ht from S, by using hig
Given a threshold A > O, we also consider the truncated model T o he, where the truncation operator A is defined by A h(x) max(min(hiss A), -A). In addition, consider both the square loss E(y, y') = (y 3/)2/2 2 and its truncated version ( = { y²)² ^ } B². This loss truncation is applied handle the noise unboundedness; see Appendix B.2 for more details.
2.1 Network Architectures
A L-layer neural network is given by ha(x) = MM oOL T .... 01 Ti(x,, where or and Ti denote the activation function and linear transform with bias at the 1-th layer, respectively. Let (1) denote the hidden state of (-th layer: 2x) = a, Ti o... o o1 o Ti (x) for / E [L] and (x)) = When it is clear from context, we will write ( = z (x) and Tiz T((z) for short. In different architectures, (Ti)/= are parameterized in different ways. M. denotes the output layer, which performs linear combination of the output features: M, o z (L) (x) W. vec(a( (x)), where W, is the weight used to parameterize M..
3

---

FCNs. R + R is fully-connected transform parameterized by Ti(z) ( z + b()) with w(l E I C and bdD) E R Here C2 denotes the width of /-th layer.
CNNs. The 1-th hidden state is feature matrix: (x) P with Dj and Cj denoting the spa- tial dimension and number of channels, respectively. Ti RP---x0--11 + BDxx is parameterized by kernel ( E R RCx X8 and bias ((t) E C as follows
CL-1
(Ti(3)
Σ 2 t=1
W JRL
+ 10, for = 1e...,,.,CC
where *a Rss x R + R& denotes the convolution with stride given by
V V*, W (v), w, Vi, "....... w...., vI. w) E R
where 1 = [Gi - 1)s 1, js] denotes the j-th patch, and v and w denote the signal and filter, respectively. As a comparison, we also consider the convolution without stride x R xI2 + k-++1 given by (v * w); = Σj WWj Note that the stride plays a role downsampling and in practice, is also common to use other downsampling schemes such as max pooling and average pooling. All results in this paper hold regardless of which one is used and thus, we will focus on the stride case without loss of generality.
LCNs. A LCN has the same architecture as its CNN counterpart but lacks weight sharing. Conse- quently, LCNs have more parameters. Specifically, the linear transform Ti Rr. 1x R Pix is parameterized by W E RRICCI-IXXD- and b(9) E RDxxC: as follows
(T((2)
Σ 1=1
2, W(l) 34.
+ b.g for = C,
where the local linear operater *y Rss x IR (v], Wr, VI w.s..... v.. Wr,), where I, = I6 1)s + 1, js denotes the indices j-th patch.
I is defined by w
Throughout this paper, we always assume the filter size = 2 for technical simplicity and thus Di 4d/22 1 for both CNNs and LCNs.
Regularizer. To regularize CNNs and LCNs, we consider following f2-type norm:
1 = |Wl12 +
((w onl boll
1=1
where aj /D, for CNNs and aq = 1 for LCNs. The factor ay introduced such that ||0||p can control the Lipschitz norm of he, thereby yielding effective capacity controls for CNNs and LCNs. See Appendix for more details.
3 Universal Approximation
The following theorem shows that deep ReL.U CNNs are universal as long as they are logarithmically deep with respect to the input dimension and the proof is deferred to Appendix D.I. Theorem 3.1 (Universality). Consider CNNs with all activation functions be ReLU. Suppose L = logg (Ad) and C = 2 for I E [L - 1] to be fixed and allow the number of channels of the last layer CL to increase. Then, the CNNs are universal: for any >> O, any compact set C [d4d and any h E C()), there exists CNN ho such that supxest hhg (x) - h² (x)] &
Proof idea. Write hg = oo First, we show there exists parameters (independent of h²) such that
(1- (x) = ( (g((z)) ((1))
a(-21)
a(x2)
o(-22)
((2dd) a(-12d) (x4s))
(0(22411) 0--12441) T (
E 2x
x(-22a-2)
((-rsa)
This implies that after L layers, the spatial dimension is reduced to 2 but the spatial information is stored to different channels in the form of
o--x))) Comparing a (4-1)(x) with the input
x, there no information loss since v; (xx)) - a(- for any E [4d]. Then, the universality can be established by simply showing that M, Tz can simulate any two-layer ReLU networks.

---

The synergy between multichanneling and downsampling. The key to achieving universality with a depth of Ollog d) lies in a unique synergy between multichanneling and downsampling. Downsampling can expand the receptive field at exponential rate, enabling CNNs to capture long-range correlations with only (log d) depth. Meanwhile, multichanneling prevents information loss whenever downsampling operations reduce the spatial dimensions. It is worth noting that this specific collaboration between multichanneling and downsampling has been adopted in most practical CNNs, such as VGG Nets (Simonyan and Zisserman, 2014) and ResNets (He et al., 2016). Our universality analysis provides theoretical support for this widespread architectural choice.
The following proposition further shows that the depth requirement in Theorem 3.1 is optimal, whose proof can be found in Appendix D.2.
Proposition 3.2. Let X' = [0, 1]dd and consider the target function (x) 2122441- I & loga(4d) - 1, then for any C N for I E [L] and any activation functions {oi]= we have infg supxxx [>)(x) - h" hx)) > 5
The intuition behind this is straightforward: If the depth of the CNN is less than logz (4d), the size of the receptive field will not exceed 2d. Consequently, functions that encode longer-range correlations cannot be accurately approximated.
The cruciality of downsampling. The following proposition shows that without downsampling, a minimum depth of (d)) is necessary for achieving universality. This highlights the importance of downsampling as enables universality with logarithmic depth (Theorem 3.1).
Proposition 3.3. We temporarily
he to denote the CNN without downsampling. Let X = [0, 1]dd
and (x) = 21 If & 4d 2. then for any Ct E N for I E [L] and any activation activationfunccionn {or)=r- we have infg supxex hx) h (x)
The proof is presented Appendix D.3. The reason behind simple: vanilla convolution (without stride) can only capture local correlations of length 2 (since our filter size is 2). Stacking L layers of vanilla convolutions without downsampling will only allow the network to capture correlations of length L + 1.
4 Efficient Learning of Sparse Functions
Definition 4.1 (Sparse function). A function f Rd + R is said to be sparse if f only depends on few coordinates. Given is E N with & < d, f is said to be k-sparse if there exist index set I= (i1,..., ix} C [d] and g: TR* + IR such that f(x) = g(xx), where X = (ri,....,
x;,) E RR.
The class of sparse functions includes functions of both functions with short-range correlations, such as fxx = ( x2). . and those with long-range correlations, like f(x) = g zz). is widely held that it is difficult for CNNs to capture long-range correlations due to locality bias. Consequently, might seem that CNNs are not well-suited to learning sparse functions like x + g z.). However, for CNNs with downsampling, increasing depth can expand the receptive field exponentially, providing the opportunity to learn long-range correlations. Indeed this has been proven in the universality analysis.
In this section, we further show that deep CNNs are not only capable of, but also efficient at learning long- maageeage sparse functions. The term "efficient" refers that the sample complexity depends on the input dimension logarithmically. This because deep CNNs can effectively identify any k critical coordinates using only Okk log d) parameters as demonstrated by the following lemma.
Lemma 4.2 (Adaptive coordinate selection for Linear CNNs). Let I = (i1, i2, it)) C [d]. For the linear CNN model he with Ci k for 1 [L] and log2 (d). Then, there exist parameters (depending on I) such that z (L) (x) = (Ii Tig D.r)
Proof. First, consider the case of = where I = (i). - a,2' be the binary representation of i. Set WI..- (1 a, az) for 1 [4] and all other parameters (including the bias) zero. Then, it is easy verify that (L) (x) (ara): see Figure 1 for a diagram illustration.
For the case of l: >> 1, set the cross-channel weights zero; for each channel, follow the case of k 1 to set weights and bias. Under this setup, different channels have no interaction and proceed in
5

---

completely independent way. As result, each channel selects one critical coordinate, and thus, ( (x) = (I' Zig. Ftc).
T4
24
48
22
TA
26
78
0
21
22
T3
24
455
26
T8
Figure 1: A diagram illustration of how CNNs select coordinates adaptively. In this case d 8, L 3. The nonzero coordinate is = 4. for which 1, 1, 02 0. The values on edges represent the weights, which are set according the proof of Lemma 4.2.
Remark 4.3. Lemma 4.2 indicates that deep CNNs are able to effectively identify any k critical coordinates with (log d) depth and O log d) parameters, which is significantly smaller than The key to this achievement is the adaptivity of neural networks, in combination with weight sharing, mulichannelingg downsampling, and depth, as demonstrated in the proof. Specifically, downsampling and increased depth allow for capturing long-rang mangrrane sparse correlations with only Olog d) depth, multichanneling facilitates the storage of information regarding different critical coordinates, and weight sharing ensures the number of parameters of each layer to be independent of d.
We now proceed to consider the learning of nonlinear sparse functions. We first need the following feature selection result for ReLU CNNs. The proof is similar to the linear case (Lemma 4.2) and deferred to Appendix E.
Lemma 4.4. Given k, m E N, consider a ReLU CNN with depth L = (4d) and the channel numbers Cj = 2k for all I E [L -] and CL m. Then for any I (f1,.... in) c [4d].
Um E IR.h and Cm R. there exists E θ such that the L-th layer outputs:
(x) (o(u) Xι + ci)....
.... ( cm)) E RR.m..
Furthermore, this CNN has (kk2 log km) parameters.
According to this lemma, deep CNNs are capable of generating adaptive features of the form: x ou Xz c) with only O(log d) depth and O log d) parameters, where the features depend only on the & critical coordinates. Note that linear combinations of this type of features give two- layer networks. Therefore, functions of the form f(x) := g(xz) with IR* + R can be well approximated by deep CNNs, as long as g can be wll approximated by two-layer ReLU networks. To measure the learnability of g, adopt the Barron regularity proposed in E al. (2022).
Definition 4.5 (Barron space). Consider functions admiting the following integral representation (x) = Jn ao (u x + c) p(da, du, dc) for all E X, where ReLU, Ω = RT x I IR and E P()). For function X + R. denote by Ag = {p (x) g(x) for all x E 2². Then,
we define
llgl| inf E [|a] (|]ul)a + [e[).. B {g ||g/| oc).
PEA,
More explicitly, the Fourier-analytic characterization (Barron, 1993; Klusowski and Barron, 2016) showed that [[9ll & [(1+11Ell1) ()(() dg. where denotes the Fourier transform of The analysis with Barron regularity is often much simpler (E et al., 2019; 2022) and can yield a better dependence on k than using traditional smoothness measures. Specifically, the Barron regularity allows obtaining generalization bounds with cimeension-indeeenne smoothness measures such as assuming E (²O 1)²), the resulting error rate would scale like D(n=s/k), which depends on & exponentially.
rates like On-11/2, In contrast, for traditional
Recall (D(v.1)) [v v A B Consider the regularized estimator given by 0, argming (1 Σn (A(TA ho(x,)),))))))))))>>>)))) 91) + >) where A, B, À are hyperparameters to be tuned.

---

Theorem 4.6. Let X' = [0.1]ar and h" (x) := g(xx) for some I C [4d] be the target function. Let k [I] and suppose g E B, sup, [g(2)| & 1, and d > For any 8 (0, 1/2), E (0,1/2), there is a choice of A, B, and X such that wap. at least 1 - 28 over the sampling of training set we have
TA o ho.
h- (P(P)
e, whenever
n > poly( Ils, k, a, log 8. log 2) (og(() (log log log log" (d) log d)s
2
The proof is presented in Appendix E.2. This theorem shows that learning sparse functions with deep CNNs requires only Ollgg d)) samples, which is nearly optimal from an reformation-thhoreee perspective. This is because Han and Yuan (2020) proved that learning sparse functions requires at least Sl d)) samples. It is also important mention that Cagnetta et al. (2022) showed that using deep convolutional kernels to learn long-range sparse functions suffers the curse of dimensionality. The comparison with our results also highlights the significance of adaptivity in neural networks.
Experimental validation. In this experiment, both short-range and long-range sparse target func- tions are considered. We set the input dimension d 4096, the sample size n = 400 and the noise level a to be zero. For the CNN architecture, the filter size is s = 4, resulting in a depth L= log. (d) 6; the number of channels is set to C = 4 across all layers. The Adam optimizer is employed to our models, and importantly, no regularization is applied. As a comparison, we also examine two-layer fully-connected networks (FCNs) with width 10, well the ordinary least linear regression (OLS). The results are shown in Figure 2. One can see clearly that even without any explicit sparsity regularization, CNN can still learn sparse interactions efficiently in both short-range and Long-range scenarios. In contrast, FCN and OLS overfit the data and fail to generalize to test data.
(000)
F (x)x)= =x +
CMA 1nd
232
Cavrznn
OLS-cou
101
12-1
Loss
1099
32.
16-1
12
539
1:00
10an
2000
2500
3000
0
520
10:0
3500
2000
2500
3900
3902
of iters.
@ of iters.
Figure 2: CNN can learn sparse functions efficiently. Both short-range (left) and long-range (right) sparse target functions are considered in this experiment. The training is stopped when the training loss drops below 10-5
Disentangle the Inductive Biases of Weight Sharing and Locality
To facilitate our statement, in this section, we denote by hg hhlon .ifen the CNN, LCN, and FCN model, respectively. We shall consider the following task.
Separation Task. Suppose the input distribution (O, Iaa) and the target function h**x)) Aoo a h² (x) where Au is universal absolute constant to be specified later and
1 h²(x)= d D -1 -
d
(2 Σ
22 - 22 x24422)
(5)
The truncation is employed to ensure boundedness of the output. However, we believe that a more refined analysis could eliminate the need for this constraint. This target function possesses the structures of both "weight sharing" and "locality" (the global sum can be computed hierarchically through local additions). We then consider the following comparisons.
CNNs vs. LCNs. This comparison allows us to isolate the bias of weight sharing as both models have the same structures, but LCNs do not have weight sharing.
7

---

LCNs vs. FCNs. This comparison allows us to isolate the bias of locality since the only difference between FCNs and LCNs the presence or absence of locality.
By these comparisons, we can evaluate the effectiveness of each bias in contributing to the improved performance CNNs over FCNs, and gain insights into how these biases interact with other structures such depth, multichanneling, and downsampling.
To establish provable separations, we need both upper and lower bounds of the sample complexity of learning h". For the upper bounds, we consider the regularized estimator given by
,, = argmin
(eA(TA ho(x,), us) + \1101
(6)
where the model hi and hyperparameters A, B, and À will be specified for each comparison. We will use the covering number-based technique (see Appendix B.2) to upper bound the generalization error. See also Appendix for how to bound the covering numbers of deep CNNS and deep I.CNs.
Establishing lower bounds is often much more challenging. We will adopt a similar approach to Ng (2004); Li al. (2020); Abbe and Boix-Adserà (2022), which involves understanding the learning hardness through the equivariance group of the learning algorithm.
5.1 Learning Algorithm, Group Equivariance, and Lower Bounds
A learning algorithm A (X' x 31)" - M(@) generates random variable taking values in θ by using the training set Sn- This definition includes the situation where our models are returned by stochastic optimizers such as SGD and Adam. We will denote d as Law(X ..aaawW
G-equivariant/iivviiinn, Let G be group acting on X. A learning algorithm A is said to be G-equivariant' i (x,,) E (X' x Vin and VT E E
(x(Tr()))))))) OO d h1 "A((x))))))))
distribution μ is said to be G-invariant for any T E G. T(X) ~ -ffX~
Sample Complexity. Given target function class F and learning algorithm A, for target accuracy > 0, the sample complexity C(A, F,) e) is defined as the smallest integer n such that
sup E hA(S.) h- l1ip()) & h K
(
where the expectation is taken over both the sampling of S,, and the randomness in A. In addition. we define the minimax sample complexity by C(F,c) == inf C(A, F.c., where the infimum is taken over all learning algorithms,, i.e., all the mappings: (X' 2)n + M(A).
For function class F, denote by F FoG. = of
F, G} the G-enlarged class.
Lemma 5.1. (A restatement of (Li et al., 2020, Lemma D.I)) Let Ag be the set of all G-equivariant algorithms. For any function class F and e > 0, it holds that inf C(A,FF,)) > C(F G,e).
This lemma shows that the sample complexity of learning F with a G-equivalent algorithm can be lower bounded by the minimax complexity of learning the enlarged class: F o G. The latter can be handled using standard approaches from minimax theory (see (Wainwright, 2019, Section 15)). the minimax sample complexity. which
Specifically, we will adopt Fano's 's method to reduces the problem find proper packing of the enlarged class F G (see Appendix B.3). In particular, when F = {f J. the packing number of F o G can be completely determined by the packing number of the symmetry group if f chosen to satisfy
o f Tall Telli | 12112.
where || |le is proper norm defined on G. Moreover, estimating the packing number of symmetry group is often much easier.
'The definition here is intuitive but not fully rigorous. We refer Appendix F.1 for rigorous definition.
8

---

Note that the specific target function (5) in our separation task is designed to satisfies (9) for the symmetry groups associated with SGD algorithms and thus, the sample complexity can be completely governed by the size of symmetry groups. Specifically, for SGD algorithms, we have
The symmetry group of FCNs is the orthogonal group Gort (4d), whose degree of freedom is ((P)). This explains the lower bound (2(d)) for FCNs.
*
The symmetry group of LCNs is the local permutation group Gloes whose degree of freedom is (d)). This explains the lower bound (2(d) for LCNs.
See the sections below for more details.
5.2 CNNs LCNs
In this section, we will derive an upper bound of sample complexity for learning h- with CNNs and a lower bound for learning h" with LCNs. The two bounds together provide quantification of the effect of weight sharing.
Consider the deep CNN hg with L = (og2(4d), C₁ = =C, 4, C₁ = for I E [2, L 1], and 01 (2) oz (x) ReLL?(x) (z), or(x) ReLU(z) for / E [2, 1].
Theorem 5.2 (Upper bound of CNNs). Suppose d > and Ao 0 and consider the estimator
On given by (6). For any E E (0, 1/2) and ô (0, 1/2), there a choice of A, B, and X such that
A o hg h
E holds w.p. at least - 26, whenever
LA(P)
n > poly(Ao. a, (og()))), (og(1/))) "(lo))))()(()))"""" d) (log log d)²
The proof is deferred to Appendix G.2. It is shown that CNNs need only Ö(log* d) samples to learn h-. The reason behind this upper bound is that h' can be accurately represented by deep CNNs with only (log d) parameters and well-controledd norms due to the well matching between the weight sharing and locality in CNNs and the unique characteristics of h..
Next we turn to establish lower bound for LCNs. Let E(::)) ) be a general differentiable loss function
and Ī kkm (0) == Σ. E(hkem (x:), 34) + r (101)).. where p > and r [0, +00) - [0, +o0).
Denote by A the algorithm that returns solutions by optimizing (=)(() for 7 steps using SGD or Adam. Under mild conditions, it can be shown that A/"" is equivariant under the local permutation group:
Gloc foc=fo fu U RAdxid, =- diag (U1, U2,..., .U) E (669) 1)}}
(10) Obviously, Gloe is group under matrix product. To ensure the Gloe -equivarviii of A. we need the following assumption, which is satisfied by all popular initialization schemes used in practice.
Assumption 1. At initialization, the fist layer weight satisfies: (1(1) j112--1 and ((1)) 5.1.2k have the same
marginal distribution for any E [Ci], k E [2d].
Lemma 5.3. Suppose that the input distribution is Grae-invariant and Assumption I satisfied. Then, for any T E N, Alen is Gloc -to-vvruivaraan for both SGI) and Adam.
The proof is deferred to Appendix F.2. Xiao and Pennington (2022) showed that under Gaussian initialization, the equivariance group of ALe is ( & Tza. which is slightly larger than Gine obtained in the current work. It should be stressed that Gloe is obtained under a much milder assumption of initialization which holds for the popular uniform initialization scheme. Moreover, we show below that the Gloe equviariance is sufficient for separating LCNs from CNNs.
Theorem 5.4 (Lower bound of LCNs). Under Assumption there exists absolute constants C, such that V E N, cD E (0, c). d, Ao > C:
C(A len =0)))))=(((
The proof is deferred to Appendix G.I. By comparing Theorem 5.2 and 5.4, we see that the weight sharing CNNs yields an ((d) improvement on the sample complexity for learning h². This highlights the importance of exploiting the "weight sharing" in h² for efficient learning.

---

5.3 LCNs vs. FCNs
We will derive an upper bound of sample complexity for learning h' with LCNs and a lower bound for learning h' with FCNs. The two bounds together provide quantification of the effect of locality.
We consider the deep LCN hipm with = logg( (4d), , C1 = Cr = 4, C₁ = 2 for I E [2, L 1]. and Ti (I) = Fr. (z) = ReLU"(xx) (1)x) = ReLU(x) for I [2,L-1] 1].
Theorem 5,5 (Upper bound of LCNs). Suppose 3 3 and Ao 3 and consider the estimator O, given by (6). Then, for any E (0, 1/2) and 10,1 there choice of A, B, and X such that
A o len 0.
h-"
< holds w.p. at least 1 26, whenever
(P(P))
> poly (o) o, (o0) ddoog
The proof is deferred to Appendix H.2. It is shown that LCNs needs Ö(d) samples to Iearn h The reason behind this upper bound that h- can be well approximated by LCNs with (dd) parameters and well-controlled norm. However, as opposed to CNNs, LCNs lack weight sharing and can only imitate the local features of h- with the "weight sharing" structure completely ignored.
Next we turn to establish a lower bound for FCNs. Let ((:,-) be a general differentiable loss function. Denote by A the algorithm: Run SGD for T steps by optimizing ( == 1 Di=1 ((h5" y/) + r ([10112), where r [0, +o0) + [0, +oo) is a general penalty function. We refer Appendix F.1 for a rigorous definition.
Lemma 5.6. Suppose that the input distribution P is Gor(Ad) (44))-iivariant and entries of W(L) are i..dd initialized from (0, ) some 3 >> 0. Then, for any T E N, A is Gon -equ-vrrvaari
This lemma was proved in (Li et al., 2020, Corollary C.2) and we state it here for completeness. It implies that training FCNs with SGD induces larger equivariance group than that of LCNs since Gioe C. Gon (4d). It is important to note that this lemma only holds for SGD, as Adam is only permutation invariant. In contrast, the result in Lemma 5.3 applies to both SGD and Adam.
Theorem 5.7 (Lower bound of FCNs). Suppose that the input distribution P is and entries of (()) are i..dd initialized from (0, 3²) for some B > O. Then there exists absolute constants C, c such that VT N. En E (0, cl, d, Ao 2 C:
C(AfF fen (h*). co) = 2()
The proof is deferred to Appendix H.1. By comparing Theorem 5.5 and 5.7, we see that the locality itself yields another (dd) improvement on the sample complexity for learning hr. This highlights the importance of exploiting the locality in h" for efficient learning.
Conclusion
In this paper. we delve into the thcoretical analysis of the inductive biases associated with the multichanneling, downsampling, weight sharing, and locality in deep CNN architectures with a focus on understanding the interplay between network depth and these biases. Our results highlight the critical role of multichanneling and downsampling in enabling deep CNNs to effectively capture long-range correlations. We also analyze the effects of weight sharing and locality on breaking the learning algorithm's 's symmetry, through which make clear distinction between the two biases: the global orthogonal equivariance vs. the local permutation equivariance. By leveraging these symmetries, establish provable separations for FCNs vs. LCNS and LCNs CNNs, providing strong theoretical support for the unique nature of weight sharing and locality.
Acknowledgements
Lei Wu is supported in part by the National Key R&D Program of China (No. 2022YFA 0022FA1008200) 1008200).
10

---

References
Emmanuel Abbe and Enric Boix-Adserà. On the non-universality of deep learning: quantifying the
cost of symmetry. In Advances in Neural Information Processing Systems, 2022. 8, 15, 36
Francis Bach, Learning Theory from First Principles. The MIT Press, 2023. URL www.h:ttpt://ttt di. ens wttp://aaccch..ppp.aa...b. book. pdf. 22
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE
Transactions on Information theory, 39(3):930-945) 1993. 6
Alberto Bietti. Approximation and learning with deep convolutional models: kernel perspective. In International Conference on Learning Representations, 2021. 15
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems, 34:18673 18684, 2021. 15
Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart. How wide convolutional neural networks learn hierarchical tasks. arXiv preprint arXiv:2208.0 00000000000,,....00000000 2022. 2, 7, 15
Arturo Deza, Qianli Liao, Andrzej Banburski, and Tomaso Poggio. Hierarchically compositional tasks and deep convolutional networks. arXiv preprint arXiv:2006. 13915, 2020. 15
Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples are needed to estimate a convolutional neural network? In Advances in Neural Information Processing Systems, 2018. 15
Weinan E and Bing Yu. The deep Ritz method: a deep learning- based numerical algorithm for solving variational problems. Communications in Mathematics and Statistics, 6(1):1-12, 2018. 28
Weinan E, Chao Ma, and Lei Wu. priori estimates of the population risk for two-layer neural
networks. Communications in Mathematical Sciences, 17: 17:1407-1425, 2019. 6
Weinan E, Chao Ma, and Lei Wu. The Barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369-406, 2022. 6, 34
Han Feng, Jianfei Li, and Ding-Xuan Zhou. Approximation analysis of CNNs from feature extraction view. arXiv preprint arXiv:2210.09041, 2022.
Kunihiko Fukushima. Neocognitron: A hierarchical neural network capable of visual pattern recognition. Neural networks, 1(2):119-130, 1988.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 2018. 15
Cuize Han and Ming Yuan, Information based complexity for high dimensional sparse functions. Journal of Complexiry, 57:101443, 2020. 2, 7
Juncai He, Lin Li, and Jinchao Xu. Approximation properties of deep ReLU CNNs. Research in the Mathematical Sciences, 9(3):1-24, 2022. 1, 2, 15
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. 1, 5.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
Meena Jagadeesan, Ilya Razenshteyn, and Suriya Gunasekar. Inductive bias of multi-channel linear convolutional networks with bounded weight norm. In Conference Learning Theory, 2022. 15
Haotian Jiang. Zhong Li, and Qianxiao Li. Approximation theory of convolutional architectures for time series modelling. In International Conference on Machine Learning, 2021. 15

---

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. 37
Jason M Klusowski and Andrew R Barron. Risk bounds for high-dimensional ridge function
combinations including neural networks. arXiv preprint arXiv:1607.01434, 2016. 2016. 6
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. ImageNet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (1111)):278222222 1998. 1,2
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, ((6):861-867 1993. 28
Shanshan Li, BaTang and Haijun Yu. Better approximations of high dimensional smooth functions by deep neural networks with rectified power units. Communications in Computational Physics, (7(2):379-411 2019. ISSN 1991-7120. 28
Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fulne-connected nets? In International Conference on Learning Representations, 2020. 1, 3, 8, 10, 15, 35, 36, 38, 44
Shan Lin and Jingwei Zhang. Generalization bounds for convolutional neural networks. arXiv preprint arXiv:1910.01455 2019. 15
Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In International Conference on Learning Representations, 2019. 14, 15, 16, 27, 28
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random
features and kernel models. In Conference on Learning Theory, 2021. 15
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. In Advances in Neural Information Processing Systems, 2022. 15
Andrew Ng. Feature selection, L1 vs. L2 regularization, and rotational invariance. In International conference on Machine learning, 2004. 8, 15
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, 2022. 15
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when deep but not shallow networks avoid the curse of dimensionality: review, 2017.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factoriza- tion and deep convolutional neural networks, arXiv preprint arXiv:2201.11729, 2022. 15
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014. 1, 5.
David R So, Wojciech Mańke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoc V Le. Primer: Searching for efficient transformers for language modeling. arXiv preprint urXiv:2109.08663 2021. 28
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018. 15, 16, 19, 40, 43, 45
Martin J. Wainwright. Highh-Dimensionl Statistiex: Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. 3, 8, 16, 21
12

---

Lechao Xiao and Jeffrey Pennington. Synergy and symmetry in deep learning: Interactions between the data, model, and inference algorithm. In International Conference on Machine Learning. 2022.
3,9, 15, 38
Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. In Interna- tional Conference on Learning Representations, 2016. 15
Ding-Xuam Xuan Zhou. Theory of deep convolutional neural networks: Downsampling. Neural Networks, 124:319 327, 2020a. 1.2
Ding-Xuit Xuan Zhou, Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787-794, 2020b. 1, 2, 15
13

---

Appendix
A Related Works
15
Technical Background
15
B.1 Toolbox for Concentrations
15
B.2 Generalization Bound for Learning with Unbounded Noise
17
B.3 Fano's Method for Random Estimators
21
C
Capacity Control for CNNs and LCNS
23
C.1
CNNs
24
C.2 LCNs
26
C,3 Comparison with Long and Sedghi (2019).
27
D Universal Approximation: Proofs in Section 3
28
D.I Proof of Theorem 3.1
28
D.2 Proof of Proposition 3.2
30
D.3 Proof of Proposition 3.3
Learning Sparse Functions: Proofs of Section 4
32
E.1 Proof of Lemma 4.4
32
E.2 Proof of Theorem 4.6
34
F Symmetries of Learning Algorithm and Proofs of Lemma 5.3 and 5.6
35
F.1 Learning Algorithm and Group Equivariance
35
F22 Verifying the Group Equivariance of SGD and Adam
37
CNNs vs. LCNs: Proofs of Section 5.2
39
G.1 Proof of Theorem 5.4
39
G.2 Proof of Theorem 5.2
H LCNs vs. FCNs: Proof's of Section 5.3
43
H.I Proof of Theorem 5.7
43
H.2 Proof of Theorem 5.5
45
I Auxiliary Lemmas for Appendix G and H
46
L.I Proof of Lemma G.2
1.2 Proof of Lemma H.3
48
14

---

A Related Works
Approximation and estimation. Zhou (2020b) established the first universality theorem for CNNs, which, however, requires the depth to increase as approximation accuracy improved. Later, He et al. (2022) showed depth of (d) sufficient when multichanneling utilized, In this paper, we further reduce the required depth to (log d) by combining multichanneling with downsampling. We also prove that without downsampling. CNNs require a minimum depth of ((d) to achieve universality, highlighting the necessity of downsampling for deep CNNs.
Deza et al. (2020) designed some synthetic tasks show the benefit of depth in CNNs. Okumoto and Suzuki (2022) analyzed dilated CNNs (Yu and Koltun, 2016) by considering target functions with mixed and anisotropic smoothness. They showed that dilated CNNs can capture long-range sparse signals if the dilation rate is on the order of (dd).. In contrast, we show that for similar task, vanilla CNNs capture the long-range sparse correlations with only Olog d) depth and Ollog" d) samples if downsampling is appropriately combined with multichanneling.
Long and Sedghi (2019); Lin and Zhang (2019) established the upper bounds of the covering number and Rademacher complexity of deep CNNs, where the effect of weight sharing was incorporated. We design concrete tasks instantiate these bounds to demonstrate the superiority of CNNs over other architectures such as FCNs. Beyond that, we also improve the covering number bound of Long and Sedghi (2019) in various aspects, including improved dependence parameter norms (from exponential to polynomial). See Appendix C.3 for a detailed discussion.
Understanding the inductive bias. Mei al. (2021); Bietti al. (2021) studied the superiority of convolutional kernels by exploiting the translation invariance of convolution. Later, under similar setups, Misiakiewicz and Mei (2022) studied the benefit of using local kernels in convolutions and the effect of downsampling; Bietti (2021); Cagnetta et al. (2022) studied the inductive bias of kernel composition (mimicking the effect of depth neural networks). However, these studies are limited to kernel methods and it is generally unclear how the results are relevant for understanding CNNs. In addition, Gunasckar et al. (2018); Jagadeesan et al. (2022); Razin et al. (2022); Jiang et al. (2021); Du et al. (2018) studied the inductive biases in linear CNNs. By contrast, examine vanilla nonlinear CNNs and show that the nonlinearity of activation functions and the network adaptivity are critical for reaping the benefits of the CNN-specific structures.
We highlight the work Li et al. (2020), where a provable separation between CNNs and FCNs was established by exploiting the equivariance groups of the learning algorithm such SGD and Adam. However, Li et al. (2020) neither disentangled the effects of locality and weight sharing nor studied the effects of increasing network depth, multichanneling. and downsampling. Xiao and Pennington (2022) took similar idea to explain the inductive bias of CNNs and other architectures but the authors focused on empirical investigations without providing theoretical guarantees. It is worth noting that the idea of studying a learning algorithm through its cquivariance group was first introduced in Ng (2004) for linear regression and was also applied to study other hardness problems in deep learning (Abbe and Boix-Adserà, 2022).
B Technical Background
B.1 Toolbox for Concentrations
Theorem B.1. (Hoeffding's inequality, (Vershynin, 2018, Theorem 2.2.6)) Let X2,,,,..., Xn be i..d. random variables with mean and satisfy X; E (a, b). Then,
2n12
X;
1
2 1
& 2e
[0-0
Definition B.2 (Sub-exponential Random Variable). For random variable X, define
|| inf > 0 [exp([XX/t) 2}
(1I)
to be its sub-exponential norm. A random variable X that satisfies || too is called sub-exponential random variable.
15

---

NN Lemma B.3. (Bernstein's 's inequality. (Vershymin, 2018, Corollary 2.8.3)) Let XN be inde- pendent, mean zero, sub sub-exponentiar random variables. Then, for every 3 O, we have
N
-02 min
1 K2
X
>
1
<
2 2exp
N
(12)
K
where K = max; ||Xill and C2 0 is absolute constant.
We will use covering number, packing number, and Rademacher complexity to measure the complex- ity of a function class.
Definition B.4 (Covering number). Let (T, be a metric space. Consider a subset K C and let > 0. A subset Kg S K is called e-covering of K if every point in K' is within distance of some point of Ke, Le. Vx E K, 32g E Ke : p (2. xo) & E. The smallest possible cardinality of an e-covering of K is called the covering number of K and is denoted by N N(K,p p.e).
Definition B.5 (Packing number). Let p) be a metric space and C T. Given E > 0, Kg C K is said to be an E-packing of K if p(z, y) for all distinet points z, y K,. The largest possible cardinality of an s-packing of K is called the packing number of K and is denoted by P(K, p,
Definition B.6 (Rademacher complexity). The empirical Rademacher complexity of function class F on finite samples is defined as
Rad, (F) = E8g sup - Σ ((())) FEF ==1
(13)
where E2........6 are i.i.d. Rademacher random variables: P(G = 1) = P(f: -1) 1. Let Rad, (F) = [F)] be the population Rademacher complexity.
The following lemma provides an upper bound for the covering number of general ball.
Lemma B.7. (Long and Sedghi, 2019, Lemma A.8.) Let be positive integer and ||-I] be a norm in RR. Denote by B, = (0 E TRP: ||0|| & r). Then, (Br [l, & (3r)² provided & r.
Lemma B.8 (Covering number of Lipschitz class). Let g : x θ - with θ RR be a general
parametric model and || || be norm over Q Define 9, = (0: ||0|| < r and G. {go ||0|| & r). Suppose for any 0, f E Op. we have [go(2) go (=) < B(2) ||0 0%1. Given 21, 22 Zn X,
let Bn = / Eim (zi) and pn(f.g) = v (f(z)) g(x,))² for any f.g E F. Then for t & rB,, we have
/BBr
N(Gr:Pnit)) &
(14)
Proof. Note that
(n go
(00(2s) go (zx))2 &
B(2))2100 0' BB, 0' ||-
n
This implies that for any > O, an t/B, -over of θ, w.r.t. || induces a t-cover of G, w.r.t. P.. Therefore,
P
3r
N(,r,Pn,:)) & <N,,,, 11114/// <
I/Bm
where the last step follows from Lemma B.7. Thus, we complete the proof.
Then we recall the uniform law of large number via Rademacher complexity, which can be found in (Wainwright, 2019, Theorem 4.10).
Lemma B.9. Assume that f ranges in [0, R] for all f E F. For any n > for any ö E (0, 1), w.p. at least 1 8 over the choice of the i...d. training set S (XI...., .n,,, we have
log (4/6)
sup JEF
Σ ((x.) - ES(X) < (ad + RV
(15)
n
n
1=1
16

---

Next, the Dudley's s integral entropy bound given below shows that the Rademacher complexity can be further upper bounded by using the covering number.
Lemma B.10. Given samples XI,...,N,, let Pr (S.9) :- f.g E and D = sups Pn(f,9) be the diameter of F. with respect to Pn. Then,
(((x)) ((xX)))((Xx)))) s(X:))²
for
Rad (1)) (1) 1
1o 1) dt
(16)
Corollary B.11. Given R 3 1, let F be set of finctions from X to 10, RJ and P be arbitrary probability distribution over X. Given n N, let X1, X2.... Xn be i.i.d. samples drawn from P. Assume that there exists Rno which may depend on the training data X1, X2,..., Xno such that 3kn,) )² ((F,Patt) < (sk.) )
for all 0 < & Kn. Then, for any (0, wap. at least 1 we have
1
plog(B] [on] + +3)
log(4/6)
sup FEF
f(X.) ES(X) & I
BV
(17)
71
i=1
Proof.
When 2R & Rnn
log, N(F, pmst) t)
di
P
2R
V Vlog(3kn/()d
71.
n
Jo
2R
2R
(Voo(33k, +1 dt +
Vlog(1/t)
V 0
Jo
(18)
2Ry log(3K, + 1) Rlg((3)
P
V
plog Kn +3)
Ry
n
When 2R > KN.
(F. dt &
Kn.
log (FF,Prnttt
2R
log logN((F,
Pm..
dt +
df
Kn
Kn Log + +1)+2)
V
/
1=++
P
2R
p plog(3)
dt
kn
(19)
2R log(3K,, + +1) + 4Rlog(3)
p
p plog( Rr + +3)
S RV
n
By applying Lemma 10,0, we have
p log( Kn + 3)
p plog(B (E[K, + +3)
Rad, (F) = [[ (F) S RE
R
(20)
where the last step follows from the Jensen's inequality and the fact that both v2 and log(2) concave with respect to z. By plugging (20) into (15), we complete the proof.
B.2 A Generalization Bound for Learning with Unbounded Noise
We first recall our setup: y: = h*(x)) + & with x, iid and & itd N((0 We assume supxex 1h" (x)) < A and denote by he parametric model.
17

---

Truncation. Due to supxex 1h* (x)l & A, we can consider the truncated model T. has which does lose the expressivity but can make the mathematical analysis much simpler. In addition, due to the noise, the labels are unbounded but the generalization bound in Corollary B.11 requires boundedness. To handle this challenge, we defin truncated loss (y, s/) = 2 (v 3/)²² B² The value of B will be specified later. For the truncated loss, we have
B
(3 < B, (CB(y.V') 2
(21)
To facilitate our statements, we define the following truncated risks
(A Ex,y [L(TA ho (x)x), v)]
(A, = Ex,y LB (T o ho (x),, y)]
LA, n
[T((TA o hx(x)), y:)]
In particular,
LA = 2 || o hg - h 11 + 70²
1
(22)
Assumption 2 (Model capacity). Let || || be norm over the parameter space & used to control the model capacity. Define H. {æ + (x) ||0|| & JJ. Denote by pH the number of parameters. Let - l| be norm satisfying that there exists a constant ar such that
||0|| < axl10llu, v0 E θ.
(23)
We make the following assumptions.
. Covering number. Suppose that there exists fm R30 + Rz0 such that
fort & (J)).. (37m(())
N(H Pn,
(24)
Note that (.)))) may depend on the training data X1, X2...., Xn and we les (J) (J)
Approximation error. We assume that there is 8" E O such that
I hg- 1>"(EP(P) & c.. and |10 & M.
(25)
Thus, (0)) & (e" + +02
The assumption (25) essentially means that he can be well approximated by our model he with the parameter norm ||0* |/ well controlled.
Consider the regularized estimator given by
0, E argmin (LAB(O)) + +1100lo).
(26)
where A, B, and are hyperparameters to determined later.
Remark B.12. Note that penalizing the upper bound (10le instead of [0]] is very common in practice. First, the constant org not too big, then this choice does not hurt the performance too much. Second, the upper bound ||0] u is often more interpretable and easier to compute than ||]|]
Lemma B.13 (Properties of 0.). For any 8 E (0, let U2
1 c.
(e.to2 + B²
2log (2/8)
M.. With probability at least 8. we have
1 LA.B(0n) < ((e,, 02) + B3²
2 log (2/0)
+ AM.
(27)
100llu & Ux.
18

---

Proof. Noting that 0* is independent of the training data, we have for any 8 E (0, 1). it holds w.p. at
least 1 that
(0) (,*)((00)
2log(2/6)
(2gg(2/))
(OA
232
& (.((0)) + B² 2
(6) 1
22g(
2 (c, + +0²) B² 2
where (a) and (b) follow from the Hoeffding's inequality (Theorem B.1) and the approximation assumption (25), respectively.
Since 6, one solution the minimization problem, we have
(0, + 0n [0.l1 &
+ + < (c. + 0²) + B²
2 2og (2/6)
+ XM,
n
Then, the conclusions follow trivially from the above inequality.
Proposition B.14 (Excess risk). Denote by 0, the estimator defined in (26). Suppose Assumption holds and B 2A. For any 8 E (0, 1/2), have wap. at least 1 26 that
TA o hg. -10112 -111eamm
BB
(B-2A)
(2(
- 6. 2
AM.
B
2A)2
Pu log (T(Ux/Om)) +3) + B²
log(4/6)
B²
n
n
Remark B.15. [J) ~ JHH, then by taking B = C(2A + a o logn) with C > 1 and \ ~ 1/ Vn. we have
M. + poly(a, A, log, log(4))) log Mc, Moglo//1//ny (PH.)
TA ha
- h2* (P(P)
Vn
(28)
Thus, we show how to set the hyperparameters B, yield standard Õ(1 V/) rate. Note that on the right hand side of (28), one Su and pH depend on the model he and we will specify them for CNNs and LCNs separately in this paper. However, it should be stressed that Proposition B. B.14 is generally applicable, which might be of independent interest.
Proof. We will prove this theorem by utilizing the following decomposition:
La( = La(θm) ((.)(
(Step 1)
+ (.,) - (A. + (..
(Step 2)
(Step 3).
Step We first need the following tail bound of V(0,a2) (Vershynin, 2018, Proposition 2.1.2): For X NO o²), it holds that
P(X > t
σ &
c
12202)
Vt > 0.
(29)
t 22T
19

---

For any 8, denote (x)) = TA o hx(x) h (x) + & where & ~ ~N(, Then, we have
(aa( - (O) - 1 E [ZZ B²) [2213
PZZ²= B² 3 1)
P
(KE) >
B2 +t 2A de
(4)
400
0
(vB= 11 2,1²2
20
dt
2 J0
V
VB +t
2A
+00
20
8
(4-2
20
ds
(s V
B
2 8
2A
20 B
1
24/2
ds
B 2A
0V2
20 B
P (( > B 2A)
PE>
B 2A
20
BB 24
20
(B 2A)² 2
where (a) and (b) follow from (29). By taking = On. we have
La(0m) LA,B(On) < (B- 2 2m
20 B
(M-24)2
(30)
Step 2. Define F, ((111))) v) + (T ho(x), ||0|| < J). Due to
|E o (x())) y) (T(TA ho (x), v) & B T ha(x) TA ho (x)
< B ho(x)) - hor
we have N(Frsin; & inequality comes from Assumption For any > 0, by Corollary B.11 and noting 7JJ = (J),
& (J)(()))()P) for & (J), where the last
It is straightforward that the following holds w.p. 1 - 8
Ph (oggBB(J)++ +
log(4/0)
LA,B(O) LA.B(0)-LAAA) [A) B²
B²
sup ||0| EJ
n
n
By Lemma B.13, it holds w.p. 1- that 100lle & Ux which leads to ||0m|| < U2/ax Plugging it into the above bound gives: w.p. 25 it holds that
log (4(8)
pn log (By(U>/ax)) + 3)
LA.B(On) -A. LA,B(On) $ B²,
+ B²
(31)
Step 3. By Lemma B.13,
(AB(O & 1 / (c( B²
2 2lo (2/8) + AM,
(32)
n
Combining (30), (31) and (32) gives
1 (A, う (c, +0? s B²/ log(4/6)
pH log (B>(U>/az)) +3)
+ B²
+ AM..
(33)
n
Then we complete the proof by noting LA (0m) =
TA o h4g - -
+ 102
L2(P)
20

---

B.3 Fano's Method for Random Estimators
In this paper, the lower bounds for LCNs and FCNs are established using Fano's method from minimax theory (Wainwright, 2019, Section 15). However, different from the traditional statistical setup where the estimator is deterministic, the estimators produced by stochastic optimizers are random. To address this issue, we develop variant of Fano's method for random estimators, which might be of independent interest.
We first recall the definition of Kullback-Leibler (KL) divergence.
Definition B.16 (KL Divergence). Given distributions Q and P, the KL divergence between them is given by
(kI(Q) = E log +00
dQ ap
when Q absolutely continuous with respect to P,
otherwise.
If the distributions have densities with respect some underlying measure vs: dQ qdv, dP = pdd, then then the KL divergence can be written in the form
(KI((1)P)= ((x) log ((x) dr(x). p(x)
In particular, we will use the fact: for p= (111,07) and Q NN 0²), we have
DkI(P))Q)= I1i N212
(34)
20
and the following lemma.
Lemma B.17. Denote by Qny Pa the n-fold product distribution of Q and P, respectively. When Q is absolutely continuous with respect to P, (KI(Qn.)), = nnDxI
Proof. This follows trivially from the fact that dQ.
diQx.-xXQ
dQ AP
dP, d(Px
θ} be set of probability distributions indexed by 0 E θ and supported on Q. Let Ze be a sample drawn from Ps. A random estimator random variable taking values in O, which is random estimate of 0 by using the sample Ze. Note that in this definition, the estimator a random variable and can model the one produced by stochastic optimizers such as SGD and Adam. In addition, when it is deterministic, this definition recovers the one commonly used in the statistical literature.
Minimax Risk. Let (Pg
+ M(0) returns
Let d θ x θ - Rgz be metric over θ The minimax risk of learning distributions in (Po 0 O}
defined by
inf sup Eg. (e, ((Z))) AEAgE0
(35)
where Eo.s means the expectation with respect to Zg and A, and the outer infimum is taken over A. ie., the set of all the mappings from Ω to M(@).
We next present a modification Fano's 's method for random estimators. The proof process resembles that of the original Fano's 's method, but with some necessary modifications. This extension, although not difficult, can be very useful as random estimators have become ubiquitous nowdays.
Theorem B.18 (Fano's method for random estimators). Suppose that for M E N and A > 0, there exists a packing 0,,...,0u. OM E O such that d (0z, 0,)² > fo, any + j. then
inf sup Eo, (((0)A))))) A. (1-
M Σ i.
log
DKL (Po. (Po,)
(36)
AEAA AEA0EE dee
M log M
log M
21

---

Proof. By Markov's inequality, Eg EE (d(0,A A P. (Ex [c(0,A(2)))]] is sufficient to lower bound
>A)
inf sup Pg (Ex d (00.AAZ)))) >4)
(37)
AEA REe
for some A > O. This will be useful for techniques based on information theory.
The principle is simple: pack the index set @ with balls of some radius 4A, that is find .1, OM E θ such that
Vi + j, d (0,, 0,)² > 4A, and transform the estimation problem into hypothesis test, that is, an algorithm going from the data Zo to one out of M potential outcomes.
To this end, we take the supremum over smaller set:
sup Poo [EA d A(2o))) A)
> max Fo, (Es [d()) ((o)))((2)))) A)
(38)
JE[M]
Any algorithm A gives test
(A(()) = arg min E& JE[M]]
E [M],
(39)
where ties are broken arbitrarily (e.g., by selecting the minimal index).
If, for some j E [M] (A((,)) * j. there exists k * j. such that E& [at (Os, (Zo,)))
<
Ea (0,, Moreover, using the triangle inequality for d(.,) :), we get:
d(, & 2E (0).A(Zz,) + d (A(Zo,))
(40)
then,
EA Al)))
1 > =d (0,, 0z) - E& [d [A(AZZ)))
(41)
3dl d 0,)² 2- -Es (A((Z))).)) 0,)))]]
(using the optimal k).
which implies RR d (0j. A (Z ))² (d](0)00)) >>>>>> > A. Thus, we have
Poz EA [dl ((o,)(Zo)))) ))
1 Po, (o(A(Zo,)) #5),
(42)
leading to
inf sup Eo.a [ (8,))))))) AEA BEA
> A inf max jE(I....Aff
Po, (o(Zo,) #1)
M
A inf
Po, (g((,,) + j),
(43)
M
which can be further lower bounded using the following lemma (Bach, 2023, Corollary 12.1). Lemma B.19 (Fano's inequality for multiple hypothesis testing). Given M distributions PL, P2..... Pas over Q let Zo, ~ Po, for j = 1,2,.... ................................ M. Then
inf M Po Zo, + 1 j=1
Σ
DKL. (Po,
log 2
(44)
g.
2 M
3.'==1
log M
where the infimum is taken over all testing methods, i.e., all maps from Ω2 to [M].
Combining Lemma B.19 and equation (43), we complete the proof. 0
In this paper, we will mostly use a variant of the above Fano's inequality for regression problems. Recall that in regression, the data are generated by y h(x) + & with x ~ P and ~ (0, o²). Let Qa be the joint distribution of (x, y) and S, = (xx, y/ ) la ==1 be n w..dd. samples drawn from Qh- Denote by Q the n-fold product distribution of Qt. Let F be the class of target functions. In such a case, the of probability distributions is indexed by h E
{Qn,h h F}.
22

---

Proposition B.20 (Fano's method for regression). Let F be target function class. If there exists 2 4A, we have
packing hi..... .......M F such that for any i # j. l|, h hg]l(2((P) La(P)
( (1-202MPTog
log 2 log M
inf sup Blllba(s.) - h (1( A. EE
Σ 1lg by -hyll2200
M
JJ'=1
(45)
where the expectation is taken over both the sampling of S., and randomness Af A.
Proof. Define d(h, h2)2 || A'lia(p): WLOG, assume that P has density function p and denote by &n the density functiinn of WV (h(xr), Then, the density function of Qn is (v))),,= Then, have
DKL (Qm,allQn,.)) - nDI.. (QxlQw))
- S p(a)dan(y) log
p(z)@x,(())
dx dy
p(x)
= n ʃ p(z) (folmte) log
2n, (v)
dy dr
22,N (1)
/ (m(z) (xx))
20 ||
h' 1111 (p))
20
where the first equality follows from Lemma B.17 and the third equality due to equation (34). We remark that this equality is also right when P does not admit a density. In this case, we can construct and verify the Radon-Nikode Lastly, by plugging the above estimate into (36) in Theorem B. we complete the proof.
derivative, and then compute the KI. divergence by the definition.
L
Remark B.21. When we use Fano's 's method (Proposition B.20) to lower- bound the minimax risk, the most important step is to construct "proper" packing. Take look at the lower bound in (45). For
fixed M E N and A > a proper packing should ensure Σi.==1 |/4 h to be as small as possible; otherwise the packing may yield suboptimal lower bound. In fact, in most applications. we will simply attempt to bound the worst-case resolution: sup;,j 1i, hg] lla
C Capacity Control for CNNs and LCNs
We first define norm the parameter space for controlling the model capacity effectively. Let (0), 120,00.-.. .2...... , Or, Wo} denote all the parameters of our network, where 0, E O₂ and W, O, denote the parameters used to parameterize Ti and Mo. respectively.
Denote by Vi the space of 1-th layer hidden state. Let Vi E R be the vectorized version of Vi armed with standard & norm and T: Vi- + Vi be the corresponding representation of Ti- Since Ti is linear, there must exist unique A O₁ - and B O + IR such that Ti ()) A(O:) vec(z(") + B(O:). Then we define
||0:]| = || == ||A(0))l22 [(0:))l2
(46)
to control the "magnitude" of Tr which ensures that for any E Vi-1 we have 7/ la < 1). Furthermore, we consider new norm over the whole parameter space θ by
|0|| = || lll +
|10.1-
(47)
It is equivalent to say ||0|| = |IM.Il ト ||Trll which is the sum of operator norms of all linear transforms.
We remark that we will show the norm (47) provides tight control of covering number of CNNs and LCNs, but less informative and interpretable. Thus, we introduce the ||0|| norm in (3) for CNNs and LCNs, which is upper bound of ||@| as demonstrated below. As opposed to ||@||. ||0||p is much more explicit, interpretable, and casier to compute. In the following, for both CNNs and LCNs, we will first derive the matrix form of T. thereby obtaining A(-) and B(-). Abusing notation, we will use Ti to denote T. for simplicity.
23

---

C.1 CNNs
Recall that for I [L] P. 1x + Dixci is parameterized by a kernel W(( RCixCe-Xa and bias b()) R as follows
C1
(T((z)) Σ
b, 8, W f4: 1 for jorj=11 = 1, Ct.
(48)
We further point that the number of parameters in our CNN is
Nenn CLDL
(2C1+ C)
(49)
A patch-based reformulation of CNNs. For technical simplicity, it is easier to take patch-based viewpoint of Ti: Ti operates on each patch with an identical local linear transform. Note that D1 = Di-1/s and we can divide (!-1) into D; patchs of the shape x Ct-1:
P ((-1))
P2
1)
x(111²=
p(i-1)
(1-1)
B for j [Di],
1zz
pf--1)
where 1 = [0j - 1)s + 1,j denotes the j-th patch. Then Ti essentially makes the following transform
p(1))(
A00 p1 1)
(-1)
A P
where A0 BaxCi-1 + xx is the local patch transform given by
Ct
(AtP), = -
L
W Wiyk + b for i = 1,2, ..... Cr.
km
In matrix form, A1) is given by
A (()) vec( () + bb
where
ve
voo(W2,..)
W
E RCx(((())))
(50)
vec (e...))
The matrix form Ti Let
こ (v veo(p!)) ,..., Tec(P(()T) e PiC.
Abusing the notation, still Ti DI- - D,C: denote the matrix form of the one defined in (48). Then, we have
Te = (1))(111) +())
(51)
where
()())
b(t)
(
b())
(1)
((1)
R
DiG
0
(1()
(())
where the block matrix has Dj blocks and ((() is given by (50).

---

The parameter norm.
By (51), it is easy to see that
|| < (
+
(())
[ 2
+
21-2
(
< | + v Di |
(52)
Then, have
||o|| ||oll
Σ Tilll & Wllll2 + Σ E(1 || F+ (Dillb()l2)) 110|p.
(53)
Lemma C.1. For any 0.6 satisfy that |il|| & and ||0'11 < J and any x E X, assume at
satisfies (0( 0 and locally Lipschitz condition (lo,(y) or(2)]l2 Qi(x) lly z|12 for any
y. E (Ti (...... on o (x)) : ||0|| < J}. We further denote (x = II== (Qi(x) + 1). Then, we have
(xo(x) - hg (x) < (1xx + 1)(1 + J ||0 - l'll
(54)
Proof.
First assume that 8, only differ in the 1-th layer, I = 1, L.
(xo(x) hx)) - Moo o o....... 00 o Ti 0
01 [x(x) M. . o T..... Ti(x)
< Lip(Mo 0... Ti 0 01.00-000000 Ti +1)
Ti T- म. (|xl|2 + +1) [T(0)0))+) (x)
Lip(Mo o...
1. (1(0)(()++)) (1 (1 Tr - (1|x + 1)(1 + J
(x) 1)
JJ J²C -
(55)
Second, assume 0, 0' only differ in the final layer. We have
(xo(x) - ho (x)] = Mo o ... 00 Ti To..... ......... o0 Ti(x) 00.00000000 o((xx
Ti(x)
< W. Wo | 0 ... Ti 00. o
W. Wol12 (x( + 1)
(56)
Lastly, consider general 0' with ||||| < J and |0''| < J. We claim that one can find 0,,... O such that
|0 < J for all E [L+1];
6' = OL+1, 0 and 0₁ only differ in one layer;
for any 1, O2 and 0.41 only differ one layer.
It is easy to check that this can be done by first replacing the maximum norm layer in 0 by the minimum norm layer in 0', and so on.
Then, by applying the telescoping sum, we complete the proof.
Theorem C.2 (Covering number of CNN). Let hg denote the CNN described in Section 2.
and define HCNN the ||0|| J}. Given X1, X2, Xn X, denote Mn
+ Σn (x:)) (Ixx)lla + 1)2. Then, we have
31M + J)z Nen
N(H t). &
(57)
t
25

---

given 0 < S.t&M,J[ + J)
Proof. The conclusion follows trivially from Lemma C.I and Lemma B.8.
C.2 LCNs
Recall that for LCNs, the lincar transform Ti PP + Ppxc; is parameterized by w RCXCCI-LDDLI and b(t) DexOi as follows
Ct-1
(T(()))
Σ
Z, to
W
J.:. + b.).
for = 1, C....
1=1
We further point out that the number of parameters in our LCN model is
Nic CLD2 C1)+4)
(58)
A patch-based reformulation of LCNs. We reformulate deep LCNs in the same way CNNs. Let z(() P:C: be the vectorized features; then the matrix form of Ti : R Pr 1 + R Ct is given by
Tiz (1)1(11) + +s())
(59)
where K()_ diag(W .... ] and Wi! E (( where
vec(W1,:.1) T vec (2 )
b D.O.
by
W
E ( g(0=
IR
(60)
vec ()
b De.i
where I, = [(j 1)8 + 1,j8].
Parameter norm.
By (59), it is obvious that
Till < || 2 + ||s
||7/00 || + (b(() |F
<
max jE(Di)
|W | ||
Thus
||||| = || +
Σ | <
[1 + > [I || = =100
(61)
In the following, provide upper bound of the covering number of deep LCNs, whose proof is nearly the same as that of deep CNNs.
Lemma C.3. For any 0,0' satisfy that ||0|| & and ||0''l| & J and any E X, assume a satisfies (0) = 0 and locally Lipschitz condition ((ar(y) - (z))22 & Qi(x) ly 2 for any y, [Ti ... 01 Tx(x) ||@|| & J}. We further denote Q (x) I (Qi(x) + 1). Then, have
hx(x)) - hor (x)l & Qa (x) 1)(1 + JY ||0 0'
(62)
The proof is exactly the same that of Lemma C.I, i.c.. the of CNNs.
26

---

Proof.
First assume that 8, 8' only differ in the 1-th layer, I = =1, I.....L L.
[ha(x) - he hx)( Mo 00 Tio .0.....00000000100..0...0000. Ti(x) MM MM.....000 Too......... 7o (x(x)
Lip(Mo 0..
- Tx()) +1)
Ti- .i (1x112 +))1++ [1(e
Lip(Mo......
L
(10e)())+1) (1 J) Ti - (1|x 1)(1 -\
[
(x) 1)(1 + J) Ti Ti
(63)
Second, assume 0, 0' only differ in the final layer. We have
(x) ho (x) = Mo o .o. 1..000000 001 Ti(x) 00 Ti(x
T...
< Wo Wo|, |1, 00. Ti 00.000000 (x))]11
< Wo Woll2 (x)x + 1)(1+ +)*
(64)
Lastly, we consider general 0, 0' with ||||| < J and |00'] < J. We claim that one can find 01...., 11+1 such that
10t|| & for all 1 [L+1]] 1];
0' O1+1, 0 and 01 only differ in one layer;
for any I, 0: and 01+1 only differ one layer.
It easy to check that this can be done by first replacing the maximum layer in 0 by the minimum norm layer in 0', and so on.
Then, by applying the telescoping sum, complete the proof.
Theorem C.4 (Covering number of LCNs). Let he denote the LCN model described Sec- tion 2.1 and define HJeN = (ho ||0]| & J}. Given X1, X2. Xn E X, denote M, =
Em (Qx(x:)) ([|xi|2++ 1)2. Then, we have
Nio
31
N(H)ON P),t)
(65)
t
given 0 < < M,+
Proof.
The conclusion follows trivially from Lemma C.3 and Lemma B.8.
Remark C.5. Note that the number of parameters of a LCN is much larger that is CNN counterpart due the lack of weight sharing. As result, the covering number of LCNs is accordingly much larger than that of CNNs.
C.3 Comparison with Long and Sedghi (2019).
We acknowledge that our proofs follow a similar approach developed Long and Sedghi (2019) but improve Long and Sedghi (2019) in various aspects.
27

---

We provide an upper bound of the covering number of LCNs while Long and Sedghi (2019) only considered CNNs. Moreover, our bounds apply to activation functions that are not Lipschitz continuous such as the squared ReL.U: a(2) =
z)² Theis activation function has become popular recently in solving scientific computing problems (Li and Yu, 2019; E and Yu, 201 8) and training large NLP pre-trained models (So et al., 2021).
The bound Long and Sedghi (2019) depends on the parameter norm exponentially. In contrast, our bound depends on J only polynomially. This improvement is critical for obtaining a sharp generalization bound for the case where the parameter norm is relatively large. For instance, by applying Long and Sedghi (2019) the setting of learning the separation task in Theorem 5.5, the corresponding sample complexity bound of L.NNs will become (dd²). ). In contrast, our bound is (dd) This improvement is very critical since the lower bound of learning with FCNs is (dd") and therefore, without this improvement, we are unable to establish the provable separation between LCNs and FCNs.
D Universal Approximation: Proofs in Section 3
D.1 Proof of Theorem 3.1
We first recall a well-known universality result of two-layer ReLU networks.
Lemma D.I. (Leshno al., 1993) Let Q be any compact in Bd and a be the ReLU func- tion. For any h E C(Q)) and any > 0, there exists a a two-layer neural network sm (x((x; 0') Σj= (u) x+ 0g) such that
sup [mm 0') - h(x)) c.
(66)
xEi
Lemma D.2 (Feature extraction). With the choice of architecture in Theorem 3.1, the exist parameters such that (1. (x) (2x((a) satisfies
(L- (x-1(()== ( (x1))
(((222)))) of (1-12441) a (x24+2)
(-x1))
(x2)
a(-x2) ((-I2dd-2
o (x2d)
a (-322d)
22x4
o (xad) ol o(-IAd)
Remark D.3. This lemma shows that z (x)-))((x) strictly stores spatial information into different channels. Note that 4d is the number of channels and 2 is the spatial dimension. The stored Atd information information is in the form of (<=;)) fi=t- Noticing t = (t) o--t), we can conclude that there is no information loss since for any RRdd + R. h(21, #2.................. ................................ xad) can be represented using the stored features as follows
((((x1) - -o(=z)), a(-22), ( - o--4aa)).
is worth noting that obviously, the weights and bias in Ti...., TL-1 do not depend on the target function h..
Proof. We provide constructive proof to this lemma. First, set all bias to be zero, i.e., ((0) for all E [T. - 1]. Next we state how to set the weights for different layers.
When / = 0, (0) = (x11 X2, xAd).
When = set W(1) E R x4x2 as follows w = (1, w
(-1,0) w
(0, T, 1,4.: = (0, -1) Under this construction, it is easy to verify that
σ (x1)
o (23)
a (rad-1)
(T(1)T=
o (--11)
o a1-23)
o (444d-1)
4x2d
(67)
o (x41)
(IAd)
0 -22
o(-24)
o(-44a))
28

---

Similarly, for 1 = 2, we can set W E R R4x8x2 such that
o (z))
σ (Tad-a)
a (
of d(-0s)
34d-3)
(x2)
σ (36)
o (xad-2)
(z(2))
o (-122)
o a(-76)
a (4-0)))))
o (23)
((77)
σ (x4d-1))
o (-x3)
o o(-27)
(---d-1))
(24)
o ((a))
σ (dad))
((-88)
o xad))
((Irss))
By induction, when 1, we have
((r1)
(2d-1)
o
o x2d+1)
(x2))
(22-22)
0--12)
o 22d+2)
(x!
E SR 1dx2
((22d-1)
o (I4d-1)
o 0---2d-1)
o(-Iid-1)
(2d))
o (IAd)
(-22d)
o a--rAd)
Specifically, the above result is achieved by setting the weights of / = 2,...,, as follows 2, For 1 & j & Ci-1 and is odd, we set
( -
w j+ijs W (1)
j+l.+t, ji+1: (1,0)
-w
((l) J.+Cr= - -Wl j+ljtCr-1: w
jiljti+C -w 1++++G 1)
Recall that W!(l) j-th output channel. Let j' = = + 1)/2 if j is odd. To prove the above result, we only show that for any E 1],
tie represent the filter used to extract the information from the i-th input channel to the
if j is odd 2 (o( o x2+2)) , (0 if is even.
(68)
We verify this below by induction.
First, the case of I = holds due to (68). Assume (68) holds for 1...., - 1, let compute ))) Without loss of generality, we only consider the case where is odd.
. When j & C1-1.
Ci
(112
(1-1)
W + (
2. #4 J,h
1=1
Z.j # Ju:: + +2 2.j+1 *, W
(1-1)
W (1)
(1-1)
j+l.j
Hence,
(Tiz (-1)) = -2i
(1-1) - bo 1j+1
11 11-1)
= -) - - = (1-12111)22
When j > C1-1 we similarly have
C
(Tz (Tz 11) = Σ
1. #e Wil)
(1-1)
ju:: + 10
i=1
(1-1)
*, (
(1-1)
(())
J-
J-CLid + 241-- 8, -
TThe following verification rigorous but not intuitive.
29

---

So
(Tiz
11-1)
11-1]
C1
2 -1
= -1
- -0-0))000-0000---000---------- = ((--21)))
Thus, the case of 1 also holds.
Proof of Theorem 3.1. By setting the weights and biases of the first L layers according to Lemma D.2, we have ha(x) = Mo o Tr. (x)) where
2 (x)
((2))
a--x1)
(x2))
0(-22) ... a(x2d) o(zad) o a(-AAA)
(1-222)
of 0(-120411 (Z22411)
a (I24+2) of (22-2d2)
By Lemma D.I, for any hi* C(Q), there exists a two-layer neural network Jm (m; 0') Σø=1, au + e₃) such that supxen Im (x; 0') h hx)) Then our proof completed by showing that we can construct appropriate Tz and MM such that the deep CNN he can simulate the two-layer neural network fm (:)
1. set CL = m, b3 = =g. For odd i, let = (i + 1)/2 and set W 1.3. = ((u))r, (uz)e42a)
and for even we set w((h) J = w(()) 1 Under this construction,
Ch-1
(x() =
(z 14- 1) *, W + blt))
4d
o
(1))) - -o(xx)) +c))
olu
2. Set Wo = (oi,...,am)) Then, the CNN hg represents exactly the same function as Sm (=):
m
m Σ ==1
ho(x)= oz
a (z( Σ ==1
(ajouux+(c) = fx(
Thus, we complete the proof.
D.2 Proof of Proposition 3.2
Given two functions f.g over X, let Poo (f.g) = supxxx [f(x - g(x)].
We prove this theorem by contradiction. First, any CNN he with the depth L < (d) can be represent as
h*(x) 91 (21, m2a) + g2 (22 x4d)
(69)
for some 91 and d2- This because that the size of receptive field no greater than 2d. Obviously, hg cannot represent long-range functions like h² (x) == 21 Specifically, we have
inf P (ho, h²) > inf sup Ig1 (x1. x2d) 92 Iad) 21 2244111
(70)
01.02 xEX
there exist gi and g2 such that
sup loi (I1, 32d) + g2(12d41,...... xEX
..., r.d) x 21224411 &
(71)
30

---

then taking special x's gives
1
(0, .0.................... + (0 0, ...................... 0)
8
9 (0,0, ........................... 0) + 92 0, 0)1
8
(72)
9 0.
0) + (1.0......0)
0........)))
In (1,0,...,0)) + 92 0, (...........
ج 8
From the first three inequalities, we have
(1, 0, ................................ 0) + 92 0)l
[1, 0, 92 0) 0. ()) (1,00,.......................... 011,,,,)))..............
0)
0) 192(0, ................................ 0) + 9: ..... 0) (9, 0, ....., + (L,
3
8'
which is contradictory to the fourth inequality in (72). Thus (71) cannot hold and we complete the proof.
D.3 Proof of Proposition 3.3
We first recall that Poo (f.g) == supxex [f(x) - g(x)l-
We prove this theorem by contradiction. First, without downsampling, any CNN with depth L < 4d can be represented as
he (x) = 91 (21, (21. .2....,,... Ftd-1) + 92 T3........ Izd):
(73)
for 91,92 In this form, 34d and 21 do not have direct correlation and intuitively, it should be impossible to represent functions like h² (x) == Vid by using this CNN. This intuition can be made rigorously as follows. Note that
inf Pro (bo. h²) > inf sup 1gn (x1, x4a-1) 1) + (2 ... rad) 2 eraa
(74)
g0. xEX
If there is 91, such that
sup x
191 x2, rtd-1) + 92(22, I4, ,..d)) x radl $ g'
(75)
then
(0, ... (0,
(0, 0, 0)
In (0, 0)).........1.............
+ (0, 0, 1) <
8
(76)
lnn (1, 0, .).....)))..... 0) 92 0,.......1.. .......0)]
0)
lg (1, O...,,....0 92 ..... 1) 1/
801
From the first three inequalities, have
|g (1,0......0 0) + 92 1)
[9, 00.,,,,....))1. g0,00 0. .......01 0) g2(00. 0, ...,, 0) 91 0....,0...00.............. g1 (0,0. ...,..))) 92, ..... 1)
(1, 920 0............. .0] (02 0. 0) + 0,... 0..
.., 0) + (0, ..... 0) 92 (0, 0, 1)
...
3
g'
which contradictory the fourth inequalities in (76). Therefore, (75) cannot hold and we complete the proof.
31

---

E
Learning Sparse Functions: Proofs of Section
E.1 Proof of Lemma 4.4
Here we prove a complete version of Lemma 4.4.
Lemma E.1 (Adaptive coordinate selection). Given k, m E N, consider a ReLU CNN model with
depth I. (Ag) and the channel numbers satisfying Ct 2k for all I ,..... I. and
Ct Then for any I = (i1,...,áa, ixk ) C [d] with & i <... < in & d. ui,..... Um E R and
, Cm E R, there exists 0 E O such that the CNN hg outputs:
z 2 (x) = (o(u, XI + (t).....,.u
+ cm)) E Ei
Furthermore, for this CNN, the number of parameters is Oh2 log d km) and the parameter norm satisfies
|10||p 2
Volloge +
Σ
I| +
Σ i=1
of + 1Wll2
In this case, the proof is the same that of linear CNNs (Lemmaa 4.2) since only need to double the channels: every two channels form a group, storing {o((z,) (-x;,)))))))))) [x))) different groups of channels proceed still independently like the case of linear CNNs. Specifically, for 1,2,.... -- we follow a similar idea to set weights and biases such that
(1- (x) = [(a), (( ((T), ((
(Ttx) (11))0(-100 ((- (xex) o (
E R 2x26
( ( o
where for any j E [k:], either t, = is or 8j = iz. Then, we set the weights and bias of L-th layer according to [ and { such that the outputs are (u, xy + a)) We refer to the following proof for details.
Proof. For any j E [k], we write the ij 's binary represention as follows
i 1-1= Σ a312
(77)
where aj, E {0, 1.. Here, "-1" is used to ensure the in E 10,24 - 1]. Next, we set the weights and bias according to the binary representation (77).
Set weights and bias adaptively:
For 1 1, w() E xx2xx2 For j E [k], set
( 21-1.11 = =- (1) (1)
2j.1; = =(1 - as,0, az.0)
For | 2,..., W E 22x22x22 For j E [k:), set
(!)) 22-1,2j-1; = wi(l) 23,21:
-w 2j-1,2j; = - -w(() 25.2j-1,: =(1 --,1-1,
For any / e [L 1). set all entries in ((()) unmentioned above and (()) to zeros.
Note that aj, E {0.1) for all j E [k] and E [L]. Thus, under the above construction, all nonzero filters are taken from {(1, 0). (-1, 0), (o, (0.
The forward selection process. Let us compute Tiz!! for I 1, 1,.... L 1. Let 88 Epr 2P,
2P, We claim that for E [T. - 1).
(Kay 22144p.1" (1-)
Fzd- T4d-2 if is odd,
(Tiz (-1))
if j is even
32

---

We will verify this by induction.
For 1 =
(Tiz! ):.j = (xi())) = x *, Wall) J.1,:
So when j is even (Tiz!)) ):sd (Tiz(0) ) and when is odd we have
(Tiz (0) ):. = (#l+ay, 33 add add-1tay
where j' (j 1)/2 above. 1 1 has been verified.
Then, assume that the case of 1, .... ,I - 1 hold, we compute (Tiz Without loss of generality, we only consider the case where is odd. Observing that
Ct (1-1) Σ
(Tiz
W
+ 6/5 Jo3
2,
!1-1) (1) (1-1)
2.j+ JJ+1.
which implies
(Tiz(11)) lis = (1 (2 2) + +
- (1 -- 12l 1(2 22 + 0z 13-1-10 (-22
I22 1(21- 122-1))88,1111
())()))) ptaya 211-1
+
Thus, the claim is verified and after L layer,
zi (L-1)) (a ) o( Fz 1)); ((
(I-1) (0(224--1))) 1( 14.1 .0122 1 1( -22-1400.--1 )-))
2,
For the L-th layer, for j 1,2, ..... set
W (1(1) 1 -W((L)
(L)
2id (uj): (1 0.,--1,0,L-11)
(5 =
We compute
(Tiz(1-1)) ):
Z * w(l)
(1-1)
j.b. + +b. 6(0))
i=1
Σ (1))((((;;))) - o(-2i,,)) + Cj
p=1
u xy + Cj.
Thus we complete the proof of the first part.
Bounding the parameter norm. Under the above construction, we have:
When I = =,2, ........4. there exists absolute constant C <> such that ||(O|r & CVT and ((0) 0. Thus, by equation (52) we have
|w + -
( &
&CV;:
Furthermore, the parameter norm in L-th layer satisfies
m
m
|
||
11
+
2
Combining them, complete the proof.
33

---

E.2 Proof of Theorem 4.6
will need following approximation result of two-layer ReLU networks.
Lemma E.2. (A restatement of (E el al., 2022, Theorem 4)) For any J E B, any probability distribution P on X' [0, 1] and integer m 1, there exists two-layer neural network (x: 8) Σ k= 0g0 (ug x + c+) where denotes the parameters {(ak, Ub ok), k E [m]] in the neural network, such that
311
If - fm(::0]
(78)
m
Furthermore, we have
Σ 5=1
layl (1u5) lcg) & 2/1
(79)
Proposition E.3. Let X 10, 1]4d. Suppose h² (x) g" (xT) with [I] k. Consider deep ReLU
CNNs with L logg (Ad) and C₁ = 2k for E [L and Ct. = m. Then, for any g" E B, there exist such that
|1 - h1"h (12(p))))) < 3
(80)
with the number of parameters being O(k² log dl + km) and
110 S Vllog d + m + 11
(81)
Proof.
Using lemma E.2, there exists a two
layer
ReLU network
Sm fm((x)
=
1 m == agd (u XI + ok) such that
3 g
(x) fm (xxx]] = (xx) - fm((x))
|us 11 + |ckl = V4:
(82)
1 laxl 2 11
m
By Lemma 4.4, we can choose the weights and bias such that the feature map of L-th layer is
z (x) (a x + e2), (u, xI + cm))
(83)
By setting the parameters of output layer W. 1 (o1,.... Am), ), it is easy to check that hg- (x) M. 2 (x) fm (x7) and the parameter number Nenn Okk² log d km).
Next, we turn to bound the parameter norm. Under the above parameter setting, we have
||Woll2 & Woll
lak < 2 1|g
u
[| + leal) = m.
1=1
Applying Lemma 4.4 gives
m
m
|10 pp S |1g"|ls + lologd
u
+
Σ ?
(84)
S11g"11 + V log d + m
Thus, complete the proof.
]
34

---

Proof of Theorem 4.6. Let H.NN = fho |101| < J}. By proposition B.14 and the covering number satisfies
N(HYNN P), (35((J)
Nenn
(85)
where (J) = for all x and log2 d for deep ReLU CNNs. In addition, note that
and Nenn = O log km). Here we use the fact that Q (x) < 2
- = J4+
M
(|2 + 1)2
< 22 J
Σ [[|x + 1)9 & v72 J)
(86)
where the second inequality follows from the Jensen's inequality since v concave. Recalling we have ar
from equation (53) and applying Proposition B.14, we have
ITTA ha.
h-- 11113 (2(P)
6 S
B²B
(B-24) 20t
+AM + BB
log(4/6) B²
Nenn log( (Bx(U>))
(B 2A)2
n
where
311g*|
M. S Vklog d + llg ll
Taking A = 1, 1, 2 c/n?, 2,,,,00 m o|l=_113 and applying Lemma B.13, we have
Vklogd+ 1s
TT hg. - - -ni12 L2(P)
0²
log(1/5)
-1/25
+
B²
Vn
n
(k2logd + k |ess (log(B) log()(U>)))
+ B21
(87)
n
where
2 log (2/0) 1 1 + B²,
/ log d + 11 + |lg
log(n(Us)) & log(d) log
21
Simplify the right side of equation (87) becomes
| o ha_ 1²" 10l1: LO(P) - - S
log poly([lg"|) [|s, k log(1//) 1/),, log log n, log(l/e))
/oatee) (log o + +) (log + log log d)
Vn
This implies that, for a target accuracy and failure probability
n n> (ll || o, log g. log ) (lg((d) (log log d)3
log2(d) (d) log d)3
22
enough.
Symmetries of Learning Algorithm and Proofs of Lemma 5.3 and 5.6
F1 Learning Algorithm and Group Equivariance
(Li et al., 2020, Appendix C) established framework to verify the group equivariance of an iterative algorithm, which however considers neither stochastic nor adaptive algorithms such as Adam. In this
35

---

section, we provide an extension of (Li et al., 2020, Appendix C) to include these situations. It should be stressed that the extension mostly straightforward compared with (Li al., 2020, Appendix C) and we provide the extension here only for clarity and completeness.
In the following, denote d as Law(A) = Law B). Let Gx be a group acting on X. Then, for any 7 E Gx and Sn [x,, yi R= let T r(S,) ((T(x:),, 1)))== We also occasionally write the group action 70 (0) for simplicity when clear from the context.
Recall that he is our parametric model and 0 E θ = IP. We make the following assumption.
Assumption 3. Given a group Gx acting on X. We assume that there exist a group Ge acting on θ and group isomorphism Q Gxx - Ge such that for all T E Gx,
lQ(((()))
hg-
The above assumption is satisfied by both FCNs and LCNs and we will verify it later. Here, we take linear regression
example to gain some intuition. In such case, he (x) (w,x). Given the group Gx = ((d) acting on the input domain, we can set Q = id and Ge = O()). Then, for any U U'EO O(),, we have hQq())(0)) U()) (Uw, Ux) (w, x) hg(x).
Suppose Assumption 3 holds. Given a learning algorithm & (X' x 2)" + M()), we say A is G Gx-eqvvvariant if S, (X x )) and T e Gx:
A(T(S,)) Q(T) A(S.).
(88)
We can also informally define the equivariance in the model space follows
(A(r(S))) O 4 ha(S.))
(89)
where ha(S.)) and hA(r(SS)) should be understood random variables taking values in the space of all the algorithms A. The definition (89) is intuitive and has been adopted in Abbe and Boix-Adserà (2022); Li et al. (2020) but should be stressed that (89) is not rigorous as it is generally unclear how to deal with the measurability issue in A. the space of algorithm. We thus will adopt (88) for its rigorous nature.
Iterative algorithm.
In the following, we will focus on the learning algorithm given by
0o ~ Pinit
(90)
O2+1 Fr+1 (O,, ... Co Sn, Ee+1) for 1, ....... T
where F; : (0)' x (X' x y)" x + θ is a deterministic update map and {T+ are i.i.d. freshly generated random variables taking values in Ω which encode the algorithm randomness and &, is independent of S,, and (0o, 01,...,0;, 0z).
Take SGD as concrete example. Let Ω (0, 1)" denote the set of minibatch selection masks and the corresponding algorithm map is given by
n Σ
(Ee+1); Ehh,, (x:), We) + >r((0..l))
Fet1 (Or, .000:...,,,,,, Oo, Sn, E(+1) = 0, T/e Vo
Note that one should not confuse & with the SGD noise, where latter is state-dependent. Assumption 4. -Pait is Ge -eeiivariaat.
V 0 DEO,tE,, S. E (X x y)n, and & E Ω:
Q(T) o Fe.1 .., 0g Sn, 5) Fr+1 ((,))((()...,,(())))).
(91)
The second assumption can be thought as that the update map F+(-) is equivariant under the joint group
action (r, Q(T)). Still taking the linear regression as an example, let (xI,...,,., E Rd be n inputs and E IR be the labels. Then, the GD update for minimizing i(w) : ||x w - y1 would be
W w, nx (X W; y) =: (w),
36

---

Let Gx Ge (d), Q id. We thus have for any U E O(d), Q(U) U and ((U)F+1((1,,3) U (w: x (XTw, W. y))
= -Uw, - (UXX) (UU)))(UW)) -y) =
which verifies the equivariance (91).
Proposition F.1. Let Ar denote the iterative algorithm (90). Under Assumption and 4, we have for any T N. bu is -x-equivari
Proof. Fix S E (X x ))" and E Gx. Let [0 and (#elro be the trajectories independently generated by the iterative algorithm by using the data Sn, and (Sn), respectively. By the definition (88), it suffices to prove that for any & N,
(0,, 0o) d
(92)
Next we prove it by induction.
When T 0, 8, 0 Puni- For any E Gx. we have Q(T) E Gg. The assumption that Piuit is Gg Ceg-invariant implies &g $ Q(T)
Assume (92) holds for T 0, 1, .l.. Let {Er} and {Er} be the "noise" used to generate {0,} and {0.). respectively. Then, we have
= (++ 0, Sn, Ee+ 9
1 (Fi+1 (O.............. 0o. ( S1+1), 0
$ (B.t1...., 0%).
where the second step follows from Assumption (4); the third step follows from the assumption that (92) holds for T Thus, we prove that (92) holds for T f 1.
By induction, we complete the proof.
F.2 Verifying the Group Equivariance of SGD and Adam Let .) be a general loss function. Consider a regularized empirical risk
(0) = ((ho(x)), + r(110)))
where p > and and r : [0, +00) + [0, +00).
At the 1-th step, let St = (i1,.... in be k i.idd. indices uniformly drawn from [n]. Define the minibatch risk by
s. (0) = S.
Σ ((hg(x4), 9:) + r((1@1))))
iES.
In each step, stochastic gradient descent (SGD) updates as follows
0.11 = 0: n7 VoLs, (0:). Adam optimizer (Kingma and Ba, 2014) updates as follows
Vi+1 = av, + (1 a a:) (VLLs,(1))
m = fm, + (1 3) v
(93)
m (1 - gt+1)
0.+1 0, 1it /v (1- a1+1 +
where 3 E (0. 1),e > 0, and the square and division should be understood in wise manner. We just consider initialization Vo mg = for simplicity. For both SGD and Adam, n the learning rate at the t-th step.
37

---

FCNs: Proof of Lemma 5.6 For h write 0 = (wi...., Wm. 0) E R", where m is the width of the first layer, w, E I for jo = L...., m denotes the weights of the first layer, and denotes other parameters. Then, we can write 4fm (x) = go(w] x,..., w w,,x) for some R x IRe-nd H I.
Consider Gx (d) and
Q:U (ug U,... U, Ip-ma)-
(94)
Let G= : (Q(U) : U Gx). Then, it is not hard to verify that Ge is a group under matrix product and Q Gx Gg is group isomorphism.
First, it is not hard to verify that the Gaussian initialization Pnit is invariant under Ge. To verify (91) for SGD, we can simply consider the case where = 1 and S, {(x, y)} without loss of generality. First, we can show that there exist functions {<)(-))?= and O(-) such that
$1 (W x, f,)xx 52(W x, x,0,)x
Fo+1 ... G. Sn, E++1) = 02 7/ VoE(Mo,(()); = 0: m)
8m (W x, 02)x O(W x, 0x)
where (W1, W Wm) E _dx=" It is not hard to verify that (91) holds for the above update
map. Then, Lemma 5.6 follows trivially from Proposition F.I.
LCNs: Proof of Lemma 5.3 Here only prove Lemma 5.3 for the Adam optimizer since the SGD case is similar to the proof above.
WLOG, we let C1 1 in the LCN model. Denote by 0 = 1,1,; the the filter weights of the first
layer and H all the other parameters, Then, 0 {0, }r} and 1,1,; E Ro, Let Gx Gloc and define
Q:U + di
(95)
Let Ge (Q(U): U E Gx). It is not hard verify that Ge is group under the matrix multiplication and Q is the group isomorphism.
First, it is obvious that under Assumption I, Puit is Gloc-invarian To verify (91) for Adam, can simply consider the case where r(.) = 0, n = 1 and Sn = {(x, y)} without loss of generality. this case, for the first step, we have
$1 *, x, 8 X/1
$2 $2 * x, 6 X12
Vol(ho (x),y)
Fi Si) 0o Co,
Oo 170
(96)
Vol(ho, (x), v))2 +c
DD, (0) x, 66 X101
0 x, 06)
for some function (s:())) and O(-). Here recall that in our paper and the local linear
operater *, k x 18 R is defined by v *, (v7 wh, vi, W V w where I, [U 1)s j.js] denotes the indices of j-th patch.
Noting (U16)) + (Ux) 0 + x for any U E Gloe. it is therefore not hard to verify that (91) holds for the update map (96). Thus we show the Gioe-equivariacee of Adam for training LCNs with T 1. The case of T > can be shown in the same way. 0
Remark F22 Note that the case of FCNs was established in (Li et al., 2020, Corollary C.2) but the proof there is not fully rigorous. We here provide a completely rigorous proof. The case of LCNs under Gaussian initialization was studied in Xiao and Pennington (2022), where the equivariance group is G @ Tza- We instead show that under much milder condition on initialization, the equivariance group becomes the local permutation group (10). It should be stressed that the major contribution of this section is providing a rigorous/unifeed I frumework to verify these group equivariance instead of yie vielding new insights.
38

---

G CNNs vs. LCNs: Proofs of Section 5.2
G.1 Proof of Theorem 5.4
By Lemma 5.1, we only need to lower bound the minimax error of learning the entarged class {h*} Gloc. To this end, need find a proper packing of this enlarged class and then apply the Fano's method, i.e., Proposition B.20. To this end, we will prove
Lemma G.I. There exist absolute positive constants C, C,,,,02 C2 0, > 1 such that if d 2 C and Ao 2 C, there exists h I2,,....
........... lim E {he) o Gine satisfying that
sup ||, h 2)1 & 02.
inf |14 h 143
hyllic(p)
7a and M 3 Cg.
Assuming Lemma G.I is right for now and applying the above packing to Fano's inequality (Proposi- tion B.20), we have
(1
M Σ
log 2 log M
inf sup
len
11 1(
3A
11g
hs ([((())
AEA ke (h* JoGbe
22 log
M
J+'==
C2n
log 2 dlog C3
1
16
20dd dogllogo c3
(97)
Taking n such that the RHS of the above inequality satisfies
Cyn
log 2
C1 =:
(98)
16
2odd
doog c3
32
gives n ()) Thus, we can conclude that C((h') Gioe; co) 12(o2d). the proof of Theorem 5.4.
Thus, we complete
G.1.1 Proof of Lemma G.1
We now show how construct a packing of {h*} Gloc satisfy the condition in Lemma G.I. The key idea is to reduce the problem to pack the equivariance group Gjoc- For U diag (U1, U2...., U2d) E Gloc. denote by U₁ xax2 the i-th block matrix. Define a metric over GJoc: for any U, U' E Gloc,
Ploc (U, = t(i U. UU}
==
(99)
In addition, we consider a subgroup of Gine:
G Gsemiloc = {diag (U1, U2..... U2a) E Gloe Uj = 12 for d}
(100)
Clearly, a packing of (T() o Gsamiloe also a packing of (Ti') o Gine. For Gremilocs we have
Lemma G.2. There exist absolute constants C, C, > O such that if d, Ao 2 C, for any T, Gsemiloes we have
PIoe(T,TT) C1
(T) d
OT 7 of & 02
(101)
Proof idea. The proof of this lemma is quite technically lengthy and is thus deferred to Appendix 1.1. Recall that A = T, h"" If there is no truncation, i.e., Ao = oo, the proof is straightforward in the sense that direct calculation gives ||h* Ot h" o o'llitp constant c. When Ao is finite but large enough, by concentration inequalities, we can expect that the truncated target function works in way similar to the orginal one. Indeed the lengthy part in the proof is estimate the influence of truncation.
cproe (T, r')d for some absolute
In the following, we show that Gsemiloe is isometric to the Hamming space:
Definition G.3 (Hamming Space). The Hamming cube (0, 1)" consists of all binary strings of length n. The Hamming distance d (x., y) between two binary strings is defined as the number of bits where x and y disagree, i.e.
(x(x, == #(i: + v()), 2,y (0, 1
We call ((0,1)" dH) the Hamming space.
39

---

Specifically, it is obvious that
(Gloes Ploc) and (f0, 1)20, dg) are isometric.
SGeemiloss Ploo) and (f0, 13d, dn) are isometric.
For the Hamming space, we have the following bounds for packing and covering numbers.
Lemma G.4. (Vershynin, 2018, Excercise 4.2.16) Let K = [ For every < m & n, we have
2
P dK, mm) > (K, m)
m k=
Proof. Without loss generality we set m as an integer. The first inequality follows trivially from the definition and thus, only need to prove the second one.
Set B,, {y E dz( y) < m). For any x E K, any k & m, there are (*) elements satisfing du (z, y) k. This is because the ways of choosing & elements from n elements are (*), and du (z. y) le if and only if and have kt different coordinates. By taking a union bound we have
[Bm,ll & Ex= (2). where : denotes the cardinality. The ball of radius m and center x can only cover most [mm,rl elements, However there are 2n elements in K. So we have
2"
2"
W(K, dd, m) sup, Bm.
(102)
k=
By the isometries and Lemma G.4, we trivially have Lemma G.5. For any 0 < m & d,
4d
PGGo Ploc: m) 2 N(Gioe Ploc: m) 2
Σ
k=
ml]
(2d)
(k)
2d
P(Gsemiloe: Ploc; m) > ((Gsemiloo Ploc: m)
Σ
k=
m
(k)
(d)
To further simplify the lower bounds, we need
Lemma G.6. (Vershynin, 2018, Exercise 0.0.5) Given in E [n]. Eizo
11
em
Proof. To prove this we only need to prove
m
k==
e
and we observe that
m
m
k
m
mm
(103)
k!
k!
k=
k=
k=
Proof of Lemma G.I. Note that for any 7. Gsomitons PIne(T,7)) & d. Then, applying Lemma G.2, we have for any h h² o H¹' h o' E {h*} o Gremiloc that
1 Mh-Miiia (2P1oo(T,TT) C2-
(104)
d
In addition, Lemma G.2 implies /|/ - - > PioooT,iTT) Thus, for 8 < LVo:: P((h*) Gsemitoe, (P(()),) N(h("} Gremiloe, (P))))
N NG sesmiioo Ploes dō² /ci)
2d
22g Σ
40

---

where the last step follows from Lemma G.5. By Lemma G.6 and taking 8 = 1
VCi, we have
2
2d
2 d
P((h} o semiloc: (P))), (Vc) 2
(105)
Ld/4 m==
(d)
(5e)
Let C3 (5e)
2 which is greater than 1.
Combining equation (104) and (105), we complete the proof.
G.2 Proof of Theorem 5.2
Let (=) == (z).U(z) this subsection for notation simplicity. We first recall the architecture of the CNN model: T = 1ogg (4d), channel number C₁ = Ct. 4, Ct 2 for 1 = 2,..., Lo 1, and activation functions 01 (z) = (2) = (1)) = (z) for = .,....
Step I: Representing the target using CNNs.
Lemma G.7. There is a parametrization 0" such that hg = h² and 110 p S log d.
Proof. We provide constructive proof of this lemma. We fist set all the bias to zeros. Then we set the parameter of the filters W E RCix01-1x2 as follows.
For / 1, w()) W.l.) (1,0), and W -W(ll (0, 1).
For / = 2, ((2) 1,1,:
-W(3) 12: 133,;
-W(2) 1,4.: (1,1) and 2,1, 1,6. for
-W((2)
i 1,2,344
12: = (1,1) and W = -w for = 1,2. For I = 3,.... 1, w!l WW
111,:
For I L, (L)
(L)
(L)
(1, W... --W()
w(T W.1.
(1, -1) and W -W(L)
for j = 1,2, 1.1.:
2.1,
For the final linear layer, W. = zd -1,--),111
First, it easy to check the output of the first two layer by direct calculation. Concretely, we have
o²
o (218-1) x4d-1)
2
(-1s)
(x())==
4x2d
(106)
[x2)
2 (ra)
(xad) o² (-I(a))
x22
2 (-(r))
and
(2(2))-=
0 {x
σ 44d-3
Iig-2
2
+
x
Edd-1
- -24d)
E R2xd
( (-1²
o ---2d--
Ad + Jii-2
2
2
+ add)
(107)
Next, we are going to prove the following conclusion for 1 = 2,....... L by induction
E 2'11 (1 [ -224)
Σ 4dd-2kk3 22. 2kk22)22
(2())==
224/22-2
k-
(12 - 222x)
k= (vāa
22a 2x
(108)
First, by (107), it holds for I = 2. Next assume (108) holds for the case of I 1 and verify holds also for the case of I.
By the definition of our CNN model, we have
(-
1.-1111 j,1. 22-112 j2211 +
(1-1) ( (1-1) (0
Z22,1 j.122 + 222.2 j.2.
(1-1) ((())
(1-1) (--
(109)
41

---

when j =
(Tiz n,1
+ (1-1) [1-11
= 2,11
2,2
21,1
2'-2
2
2k 122-++ 12/ (221-2121-1 - -2zh + (2i-))))))
+
2k (2--1122-1)2-111 - -22 2hh--22 12:-122)))--
k=
k=1
2
= Σ
2 21-1+((11)2
2 x22+((-112))
k=
which verifies (108) for j = 1. The case of j = 2 can be verified in the same way.
So by now we have verified that the output of the L layer is
d 1= (- i= -12111
x2.)
Σ -= ( 22+22-11 - x22042)
(2(
o
x220422) -
R22x2
(110)
Σ i=1 (12042211 - 2
d
Noting (xx) 0(22) x, we can recover Σ -i=1 using the feature stored in (!
(1
-22;) and Σ (22 2222-
22242al by
Recall that in our last layer, our activation function (L( = (x)), and we have o² o2(x)+o2(-x))
x². Noting that 4a,3 = (a 3)² (a B)² and viewing Σ (2 222,, Σ (x 221-2-11
(2)) as a and respectively, a simple calculation would lead to hgg (x) h" (x).
Note that for all
[L]. ((9) 0, C < Then, it is obvious that there exists an absolute
constant C > 0 such that || E for any E [7.] and ||oll2 < C. Thus, we have |10 1pp = ||Woll2 Σt || T. log d.
Step II: Estimating the sample complexiry.
Recall the input distribution P = (0, Tad). Let HGNN (ho ||0|| & J). where we recall ||||| is defined in Appendix C. By Proposition 1.1,, the covering number satisfies
(3%)(1))
Nenn
N(HLNN -ia,t)
(111)
where (J) - M,, J) M, V E. (Qx();)) ([|x)ll2 + 1)2 and Nena Olog d). We will use the fact that logg d
First, we turn to the estimate of Qo (x:). To this end, we give simple lemma to estimate the local Lipschitz constant of our activation functions.
Lemma G.8. for
|æl. 1vl < M, we have 18(x) ((v) < K |æ - y) then we will have
[1 3(y)ll2 < K ||x yll2
for any ||x||2 : 11vll2 & M.
Proof. [1x(x) - B(y) (,((,)) - B(v:)) & K2(r, v1)² =² || 2
Our (1(+) on(-) 0²(.) activation functions are 2K Lipschitz continuous when restricted
in [-K, K]. So for (x:). since (xx))l2 < ||Ti|| ([|x:ll2 + 1) & J[[[x1l2 + 1), we have
(x,x,) < (1x(12 + 1). For (x,,.. we similarly have
|T o ................................ o o (xxx) & (1 + +)*+1 +1)
so Qxx;)) & 2) L+1 (1|x 2 + 1)2 is straightforward. Thus, Qx & 22++2 L++ (11x
1)a. Therefore, will have
(J) = E (i (J)) S J(1 R. B[M
$ J(1 2222+224+2
E E[[[|x|] + 1)81 S &J(11 J)2++224+2
(112)
42

---

where the third step follows from the Jensen's 's inequality and the fact that 2 + v2 is concave: the last step uses the higher-order moment bound sub-exponential random variables (Vershynin, 2018, Proposition 2.7.1).
Recalling have oh from equation (53) and applying Proposition B.14, we have w.p. least 1 20
TA hā. - hr" 10112 L2(P)
o²B
LB 2,1
log(4/6)
Nenn log (T(Ux))
-a S (B - 2A)2
20
+AM. B²
+ B²
where
=,
M. S logd
Taking A= AA, B = 2A + Vloooognn n, X 1 and applying Lemma B.13, have
IITA o hg. - 11-
-1 (A(P) < poly(An)
0²
log d + B² log(1/6)
+ B² log d(log(B) + log( (Ux)))
Vn
where
log (2/6)
log(>(U>)) S log(d) log
0² + B²
+ log
21
Simplify the inequality, have
log log d log log log d
A o ha. This implies that, for a target accuracy and failure probability 6,
ht (P(P)
& poly(Ao, (18) log log n)
vnn
poly (a, log 8 log - - log d(log log d)3
enough.
H LCNs vs. FCNs: Proofs of Section 5.3
H.1 Proof of Theorem 5.7
Under the assumptions in Theorem 5.7, Lemma 5.6 implies that Afr is Gan(4d)-equivalen, Then, by Lemma 5.1, we have
C(A fen (h*),)) C((h)} o Gon (4d(4)),))
We next use the Fano's method (Proposition B.20) to bound the right hand side, by which the key to obtaining a tight bound is to construct a packing of (h*) o Gon (4d) large as possible. Specifically, we will prove the following lemma.
Lemma H.1. There exist absolute positive constants C, Co 0 such that if d,, Au > C, there exists hy, I2,,... ha E (h*} } a ((d)) satisfying that
sup 1h+ hyll22(p) Co. inf ||,, b
h
cs. and M > 2)/2-1)/2
ifj
Assuming Lemma H.1 is right for now and applying the above packing to Fano's 's inequality (Proposi- tion B.20), we have
M
inf sup AEA he eh o0(ad)
E. [1haass)) - h [[(2pp) 21
-11112((p))
1
|1 - h2 h11l
log 2 log M
20
M log
M
1
Cg
2
7
r2d(d
logg2
d(d -
Taking n such that the right hand side to satisfy
C67
2
C5
Cs
<
cg
o²d(d - 1) log
d(d 1)
8
gives n = 22(22))). Thus, we can conclude that C((h*) } G (4d), En) (2)2d))) Otherwise, the minimax error becomes larger than Eg.
43

---

H.1.1 Proof of Lemma H.1
We now turn to construct proper packing for {h*} } (4d)) to satisfy the condition in Lemma H.1. To simplify the statement, define y IRdd + R and gu Red + IR for U E Rdxd by
d
(xx = Σ
( x gu(x) = =Xi:AUX44.200 Xx411:2d.
i=1
Lemma H.2. (A restatement of (Li et al., 2020, Lemma D.2)) For any U E Gorld), there exist TU E (2d) such that
go (x) = (x).
This lemma implies that for any U E Gon(d),
d
1 ā (xdaUUxa-1:22)
Σ
(121+22-1 - -224+22) = -d-ag (x
TV (7)
= ht-h
(x) E {h²} Gon(4d),
(113)
12d
where we slightly abuse the notation: using f (x) denote the function f()).
Let
{{
Σ 2224422-1 22-1 x22122)) ) U Gon(d)
Uso
TAo e fo fx(x) d (x(xt1x4+120))
(114)
Note that equation (113) implies
Uso C {hh} God(
Next, the following lemma shows that when the target truncation threshold Ag is large enough, finding a packing of (MA. || (p)))))) thus a packing of ((h) Gon (4d), I1-1l can be reduced to pack the equivariance group (Gon (d). (d
Lemma H.3. There exist absolute constants C, C32 C4 > such that when d, Ao 2 C. we have for any U, U E Gon(d) that
C3
U - d
- T fo To o Su &
C1 IU U' d
Proof idea. The proof of this lemma is technically lengthy and deferred to Appendix I.2. Note that when Ag = -0, i.e., there no truncation the target function, simple calculation leads to
E (X) for (x)) 4 U - U
d
When Ag finite but large enough, by concentration inequalities, we can show that the influence of truncation is negligible, although the proof is lengthy.
Lemma H.4. (Li et al., 2020, Lemma D.4.) For any positive integer d > and any positive e & 02/2, have
did
P(G a /Vd.e) C2
where Cj and 02 are two positive absolute constants.
The above lemma provides lower bound of the packing number of (d), I0 Intuitively
speaking, this lemma is true due to the fact that Gon(d) can be viewed as d(d-1) compact manifold from Lie group perspective.
2 dimensional
Proof of Lemma H.I. First, for any U, U' E Gon(d), we have
IIU U' < 2(1UU]] 11'1) 4d.
44

---

By Lemma H.3, we have
Aa TA ft lip() <
< |1 U <
4c4.
(115)
By Lemma H.4 and taking 6o = 02/2, there exist Ul...., UM E Gon with M >> 2 did-1
2
such
that ||U, - Usll > covd for any + j. Thus, by Lemma H.3, we have for any o that 2e1
C3 G
A Jt. To Suy [PP(
d 4c
=:
(116)
Combining (115) and (116), we can conclude that ( condition in Lemma H.1. Thus, we complete the proof.
fuy 1 are packing that satisfy the
H.2 Proof Theorem 5.5
Let (=) (eLU(22) in this subsection for notation simplicity. We first recall the architecture of the LCN model: L log, channel number C₁ = Ct, 4, C₁ for = 2.... . and activation functions o1 (z) = (z(2) (z), (1)) (2) for 2, L
Step I: Representing the target using LCNs.
Lemma H.5. There is a parametrization 6 such that h = h and |10 p S d.
Proof. With the same depth, activation functions, and channel numbers, LCN can simulate its CNN counterpart. By the proof of Lemma G.7, the exact representation is obvious. The parameter norm bound is due
|0||. ||
Σ I=1
Eaw 1I++ +||b((
log d+2
4d 2 S d.
S 51+ Σ
[Di+ +0) = =
Σ
1=1
Step II: Estimating the sample complexity.
Recall the input distribution P = (0, Taa). Let HJEN = (hg ||l|| < J). where we recall ||||| is defined in Appendix C. By Proposition B.14, the covering number satisfies
(J)
Nica
N(HOON t)
(117)
(x,) (Q (1|x;112 + 1)2 and Nicn (d). Here we use the fact that T, = log, d + 2. Following the same argument as in Appendix G.2 we have
where -J) M1+ M, = V
(xi) & 21+2 + (1+ J) 1|2 + 1)3. Therefore, we will have
((J = E Frm (J)) $ J(1 JY E[M,]
((1 + 22 |[[[|x|2 +1s| S JJ(1+ J)2L2222
(118)
where (a) uses the Jensen's 's inequality and (6) follows from the higher-order moment bound of sub-exponential random variables (Vershynin, 2018, Proposition 2.7.1).
Recalling we have au from equation (61) and applying Proposition B.14, we have with probability at least 1 25
ITA o ha.
h² 1-12 12(P)
c.
(B 2A
G3 B
(B (B-24)
20
+AM M B2
log(4/0) B²
Nion log(Br(Us))
n
where
E, O,
M. S d
45

---

Taking A = Au, B 2A + log A = 1/ and applying Lemma B.13, we have
| o h0, -h 11 1P(P)
0²
logd
log(1/6)
d(log( (B) + (Ux()(U))))
& poly(An)
+ B²
+ B
vn
nz
72
n
where
1
2 log (2/5) B²
log(>(U>)) & log(d) log
0²
d
21
n
Simplify the inequality, we have
log n dylog + log d
Ao hgg 11" LP(P)
< poly(An, o, (1/))))) log log n)
n2
This implies that, for target accuracy and failure probability 6,
poly(Au, o, log log 1 ) ddoog
is enough.
I Auxiliary Lemmas for Appendix G and H
Recall our input distribution P -N Laa). Recall that target function h = Ao
where
h*(x) =
Σ 2 1 22x))
2 Σ
22422
22 222
In the following, we show that the truncation operator A, on h² U for any E GAn will not matter a lot when Ag is moderately large.
Lemma L11 Ler X P. For any U E Gon(4d), there exists one absolute constant Ct > O such that for any E (0, 1), if Ag 2 max (Iog(4/6)
(4/6)) ). it holds that
d
P (TTAD o h² U()) h²t U(X) 1
Proof. Without loss of generality, we can set U = Lid since P is invariant under Gon(4d). For simplicity, let Y; X2 X2 for i [2d] this proof. is easy check that are i.i.d, random variables with || li S 1. Then, using the Bernstein's 's inequality (Lemma B.3) gives
Σ
Y
dt
Y
2e -o min( Vdt,t²)
where C1 > 0 is one absolute constant. Setting the failure probability be smaller than 8/2: 2e-a min(t?, (Vat) < 5/2 gives max (Viutario) log(4/8) aivd
Cs- This implies that it holds
C1
w.p. at least 1 - 6/2 that
Σ
Y
< CaVd.
Similarly, it holds w.p. at least 1 6/2 that
2d
Σ
Y
CoVd.
#=d-1
Combining them leads to
P( o hxx)
C3 1-6
46

---

L.1 Proof of Lemma G.2
For any T = diag (U1, U2,..., U2a), T' = diag (U1, ,,,,...u0 .,2a) E Gremilors let
I [2d] : U, + U/}
be the set of indices where the local permutations are different for and T'. Let s [I]. By the definition of Gemiloes we must have j < for any j I. Thus, have
h" -x) - 1t' ox)
2
E -22y)
Σ
224122) (119)
jEZ
where oj E (+1,-11 for j E I. Because of the symmetry of P, we can assume oj = 1 for all j E I without loss of generality.
Upper bound.
First, recall that X ~ NO, Iaa), we have
hi T h' orort 7 oTIILA(P))
E Ao he o T(X) Ao o (x)
E
o T (X) - h or (
27
E
Σ
X 11
Σ
XX xd++2-11 - 1 -X3e+2))
d2
JET
4 E
Σ
(x 2
E
XX 2d+ - x2d+22)
de
JEI
4 Var
Σ
(X2 -X2i)
Var
Σ
(x (x - 1 -X20+2))
d²
jEZ
1=1
4
sd
(Var (Y 2²
d²
64s
(120)
d
where ~ ~ (O, 1) are independent random variables.
Lower Bound, Denote the events
E TA o = o
11x Eg =
for the lower bound, we have
| - h²- o''lii(( > E |1 Ba (arn),(())))) (X) h
h- o o (x))²²
E [h" T(X) - o TX))
(han o
E (h* T r(X) -h" o
P(E Fa)) E (h* T((X (
(121)
where the last inequality follows from the Cauchy-
Schwarz Cauchy-Schwarz inequality: (EYZ)² < EY
For the first term the RHS of (121), have from (120) that
E (h' o T(X) - h² ox))) 64s
(122)
47

---

For the second term on the RHS of (121), we have
d
E [hh T(x) h- -()))) =
16
E
Σ
(x2 11
Σ
X 2d - -X
dt
jET
d
16 dt
Σ
(x3 -
E
Σ
(X
25 2d X2(+20)
JEZ
(123)
We first compute the first term by expanding it.
E
Σ JEI
1
(x2
- x2,
B (x2 X2, - -220
WJEZ
where we use the fact: E - X2,) (2 x2,)²1 O(1) for i,j. By the same argument, we have
d
E
Σ
(x2 212-424-1 X2H22)
S d2
(124)
That leads to the following estimate: there exists an absolute constant C3 >> 0 such that
s²
E [h r (X) h ((X)))
C3 d²
(125)
By Lemma I.1, there is an absolute constant C such that when Ao > C, we have
P(E
(126)
C3
Plugging (122), (125), and (126) into (121) gives
h or h o oo = 7
64s
63s
(127)
Combining the upper bound and the lower bound, we complete the proof.
1.2 Proof of Lemma H.3
For any U E Od),, let by = Ao o fo with
1 fu(x) = d (xIT Ux 1:2a)
Σ
(22 (22442111 2224425)
Thus, we have by E (h*} Gon (4d) due to Lemma H.2.
Upper Bound.
We have
|be - ho lipp(r) E [ITAD o fX((X) TToo o St (X))²
< E (fu (X) - for (X)))
(U - -U -U')UU-")Xaaaaa (') 2
Σ
(x2 (X24+2111 - -x21-22)
27
E [XTTa(U (1)Xa41222)) ?]
(x2 X24411-1 - X2
-X2d-22)
(128)
48

---

where the last step follows from the independence between X1:2d and X2d+1:1d-
Note that by equation (120),
)
E
Σ (X3
2d+2i-1
XX
4d
(129)
And, for the first term, we have
E (" X2)22
|
=E E (x (Ta U') X2+1222))) [xa+12d]
E E
- U X XI Xe
E [X -U') - -U--""Xa+a -U))aa+122)
Tr ((U U²) TOU (UU-UUU))) -U'))
UU - 1' U'
(130)
Plugging (129) and (130) into (128) gives
4 - -
[ - ho (2p(p &
d
Lower Bound.
Define events
ES {x A fu(x) fo(x)}
Eg = fx TAi o fxr (x)(
Then, we have
Iihe her her11 > (f()) (x))
E ((x - E (1
Jun
> E - E2)) (x fuu((X))
-
- (131)
where the last step uses the Sauuhh--chhaatt inequality: (E[YZ))* < EY We next bound the two terms of the right hand side separately.
For the second term, we observe that
1 B (XTa(U- -U)xaaU' - -X
E (Vf((X) for (X)) =
X2
2d42:-1
=
d
1
E
[xTTal - - U2)x4+12d)) "I E
Xx3 222 - -X3a)
1 - U') -X') UU'XXa
(132)
de
where the last step follows from (124). Note that conditioned on X4411224
XT - Xa (O., IIUU - U') X
Combining with the fact that EY = 3 for Y ~ ~N(00 we have
E (XTT'UU- - -U') 4 '1 33 |I(U U') U')Xa+122d11)
49

---

Let B - Z N(0,1.) and B B = D. Then,
E [I(U - U*) Xa+12d112 = E [Z DZ)
=
Σ ZigZiZj
Σ
Di, IE [2,
1
2 D 2 < BB = - U'
(133)
Plugging (133) into (132) gives
U - U'I
E [[]o(X) - fo. (X)) <
(134)
d²
for some absolute constant > 0. By Lemma 1.1, there is an absolute constant C such that when Ag C, we have
1 P- E2) <
(135)
C4
Continuing the equation (131), we have
Ilky hvr (12r1 > [X/o(X) - [ex(x)) - v (1 P(F) F2))
(X) fc.
1
| 1
> (X) - fex(x)))
-1
C4
d2
1 'IU U1
11 - U
d
IUU - U'
(136)
where in the third step the result from the above upper bound:
4|l0 1Z
E ( (x))
Combining the upper bound and the lower bound, we complete the proof.
50


Reviews:
[{"review_id": "V5jXYvfigS", "reviewer": "Reviewer_35ph", "summary": "This paper studies the inductive bias of deep convolutional neural networks (CNNs) in three distinct ways. With $d$ the input dimensions, it is shown that (i) depth $O(\\log{d})$ is sufficient to achieve universality, i.e. the capacity to approximate any function of $d$ variables, when there is downsampling between layers; (ii) all sparse functions can be learned with $O(\\log^2{d})$ samples, close to the optimal $O(\\log{d})$; (iii) both weight sharing and locality of the connection are crucial for achieving the nearly-optimal sample complexity.", "questions": "1. Regarding the difference between CNNs and LCNs, Bietti et al. (2021) provides a very simple explanation of why there should be a factor $d$ of difference between the sample complexity of a LCN and that of a CNN. Is their argument valid also in the setting of section 5?\n\n2. Is there a simple explanation based on symmetry as to why the sample complexity of FCNs presents another factor of $d$ with respect to that of LCNs?\n\nThe following are not questions but suggestions:\n\n3. There is a typo in line 12 of the abstract (separete instead of separate).\n\n4. In the same line of the abstract I would use a different word than `introduce', since locally-connected networks have been introduced before.\n\n5. Could you please quickly recall the meaning of the various big-O notations in section 1.2?\n\n6. State explicitly that this work considers CNNs with nonoverlapping patches at all layers. e.g. in section 2.1.\n\n7. The related works section needs further references, for instance, the aforementioned Poggio et al. (2016), *'Why and When Can Deep – but Not Shallow – Networks Avoid the Curse of Dimensionality: a Review'* and other works of the same group. Schmidt-Hierber (2021), *'Nonparametric regression using deep neural networks with ReLU activation function'* is also relevant. Furthermore, Bietti (2021) and Favero et al. (2021) *'Locality defeats the curse of dimensionality in convolutional teacher-student scenarios'* studied the benefits of locality before Misiaciewicz and Mei (2022), and Xiao (2022) *'Eigenspace restructuring: a principle of space and frequency in neural networks'* also studied the inductive bias of deep CNNs in the kernel regime.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Our theoretical understanding of deep CNNs is still very limited and this paper has the potential to provide a solid contribution to the topic. The explanation of how multichannelling and downsampling conspire to achieve universality with $O(\\log{d})$ layers is nice and intuitive. The result of Theorem 4.6 on the sample complexity of learning sparse functions is novel and interesting. The separation results start from a known idea  (using the symmetry of an algorithm to unveil its limitations) but give significantly new insights into the separate roles of weight sharing and locality.", "weaknesses": "Overall, I believe this paper would be a valid contribution to the community but there are some issues that I would like to see addressed before recommending publication. \n\nI like section 3 and I believe it is a valuable addition to the literature, but I would downplay the claim that all previous results required a depth of $\\log{d}$, as currently written in the abstract. The idea that sufficiently deep CNNs achieve the same expressivity as fully-connected networks (hence they are universal) has been there for a while and the difference between $d$ and $\\log{d}$ is solely due to the amount of stride included in the architecture. The case considered in this paper, where the stride equals the filter size, is commonly referred to as *nonoverlapping patches*---the authors should say it explicitly at least in section 2.1---and it has been studied in several other works, including some cited in this paper such as  Cagnetta et al. (2022) and some that are not cited but should be such as Poggio et al. (2016), *'Why and When Can Deep – but Not Shallow – Networks Avoid the Curse of Dimensionality: a Review'*. Both these works imply that deep CNNs with nonoverlapping patches and depth $\\log{d}$, so that the post-activations of the last hidden layer look at the whole input, are universal.\n\nThere is also something about theorem 4.6 that I think requires further explanation. As far as I understand, theorem 4.6 uses lemma 4.4 together with the generalisation properties of one-hidden layer neural networks (theorem 4 from E et al. (2022)). If this is true, then I do not understand why one needs a deep CNN to achieve sample complexity $O(\\log^2{d})$: the result of lemma 4.4, i.e. that there exist a set of parameters such that the $L$-th layer outputs the right-hand side of Eq. (4), is also applicable to the post-activations of a  one-hidden-layer fully-connected network. I should remark that my concern might be due to a misunderstanding of the proof idea, but if that is the case I will be happy to raise mi mark after rebuttal.\n\nFinally, the symmetry-based lowe bounds like those of theorems 5.4 and 5.7 can usually be explained very well at an intuitive level. I think not having such intuitive explanations is a weakness of this manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and questions and we will revise our manuscript accordingly.  In the following, we response to the specific weakness and questions. \n\n(1) **CNN with non-overlapping pathces and the universality** [Weakness 1; Question 6,7]\n\nFirst of all, we agree that we should have emphasized in the beginning of the paper that we are consid- ering CNNs with non-overlapping patches and discuss related works, in particular the papers mentioned by the reviewer, of studying CNNs with similar architectures.\nRegarding prior works on universality for CNNs with log d depth, after reviewing the two highlighted\npapers, we observe:\n- Both papers indeed discuss CNNs with non-overlapping patches.\n- Neither paper addresses the universality problem.\n- Their analyses do not directly lead to universality conclusions similar to ours. A significant gap in their studies is the absence of revealing that multichannels can be used to store extra information when reducing spatial dimension with stride/pooling.\n\nIn the following, we provide detailed comments for each paper.\n- [Cagnetta et al., 2023] investigates the inductive bias of NTK with deep CNNs that use non-overlapping patches and have infinitely-wide channels. First, [Cagnetta et al., 2023] did not examine the univer- sality and it is generally unclear if the associated kernel is universal. Second, [Cagnetta et al., 2023] focuses on kernel regime, which is very different from CNNs in adaptive regime. For example, in adaptive regime, that the number of channels to be O(d) for all except the last layer suffices for achieving universality.\n-  [Poggio et al., 2017] hightlights that deep locally-connected networks can learn functions with similar hierarchical structures efficiently, while shallow fully-connected networks cannot. [Poggio et al., 2017] emphasizes the role of locality in separating deep CNNs with fully-connected networks. Their study does not touch upon universality and centers on locally-connected networks, not CNNs. They use multichannels in their analysis, but does not reveal its role in maintaining information during spatial dimension reduction.\n\nIn summary, while both works are valuable, they do not explore universality as we do. Their contexts are distinct from ours, making direct comparisons challenging. Furthermore, the foundational insights of our study differ notably from theirs.\n\n\n(2) **Learning Sparse Functions.** [Weakness 2]\n\nLemma 4.4 demonstrates that deep CNNs can achieve the variable selection $\n(x_1,x_2,\\dots,x_d)\\mapsto (x_{i_1},x_{i_2}, \\dots, x_{i_k})\n$,\nreducing the spatial dimension to $O(k)$ by using only $O(\\text{log} d)$ parameters, facilitating the efficient learning of sparse functions. In contrast, fully-connected networks can achieve the same variable selection, but they necessitate a minimum of $\\Omega(d)$ parameters (a single neuron already requires $\\Omega(d)$ parameters). Consequently, fully-connected networks demand at least $\\Omega(d)$ samples to learn sparse functions, unless specific sparsity regularizations are imposed. \n\n(3) **Symmetry-based lower bounds and the intuitive explanations.** [Weakness 3; Question 2]\n\nOur intuitive explanations are given as follows. \nDenote by $\\mathbb{A}$ the learning algorithm and $G$ the correpsonding symmetry group. The inherent symmetry ensures  that learning $f^*$ is equivalent to learning the $G$-enlarged class $f^*\\circ G := ${$x\\mapsto f^*(\\tau x): \\tau \\in G$}. Thus, the sample complexity of learning $f^*$ by $\\mathbb{A}$ is lower bounded by the packing number of $f^*\\circ G$, which, in turn, is further controlled by the packing number of the symmetry group $G$ when  $f^*$ is chosen to satisfy \n\\begin{align}\n||f^*\\circ \\tau_1-f^*\\circ \\tau_2||_{L^2(\\gamma)}^2 \\sim ||\\tau_1-\\tau_2||^2_G,\n\\end{align}\nwhere $||\\cdot||_G$ is a proper norm defined on $G$. Thus, the sample complexity is fundamentally governed by the size of the symmetry group.\n For SGD algorithms, we have\n- The symmetry group of FCNs is the orthogonal group $G_{\\mathrm{orth}}$, whose degree of freedom is $\\Theta(d^2)$. This explains the lower bound $\\Omega(d^2)$ for FCNs.\n- The symmetry group of LCNs is the local permutation group $G_{\\mathrm{loc}}$, whose degree of freedom is $\\Theta(d)$. This explains the lower bound $\\Omega(d)$ for LCNs.\n\n(4)  **The argument in Bietti et al. (2021)**\n\nIf our interpretation is accurate, [Bietti, 2022] contrasts shallow CNNs (encompassing 2-3 layers) with and without global pooling within a kernel regime. From the standpoint of sample complexity, introducing global pooling provides a factor d advantage, provided the target function aligns with this architecture. Therefore, in our humbble opinion, the inductive bias studied in [Bietti, 2022] is distinctly different from inductive biases associated with locality (LCNs vs. FCNs) and weight sharing (CNNs vs. LCNs).\n"}, {"review_id": "ikIWU83KXW", "reviewer": "Reviewer_mzq4", "summary": "This paper provides a fundamental analysis of the superior performance of CNNs, specifically focusing on their downsampling and multichanneling capabilities. Moreover, it establishes evidence with theoretical guarantees that CNNs exhibit efficient learning of sparse functions compared to FCNs, attributing this efficiency to the weight sharing and locality properties inherent in CNNs.", "questions": "1. In lines 158-159, the authors assert that \"universality can be established by simply showing that ... can simulate any two-layer ReLU networks.\" It raises the question of whether the authors assume that a two-layer ReLU network can approximate any continuous function.\n\n2. Could you please provide more context or specify the notations in Assumption 1 you are referring to? This will help in understanding Assumption 1 and the difficulties in following the notations.\n\n3.  It would be better to provide a summary of the technical novelty of this paper.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper presents a comprehensive and rigorous theoretical analysis of the intrinsic inductive biases linked to multichanneling, downsampling, weight sharing, and locality within CNNs. It introduces a new theoretical framework that characterizes the crucial role of multichanneling and downsampling in empowering deep CNNs to efficiently capture long-range dependencies within the target function, yielding valuable insights into their operational mechanisms. Furthermore, leveraging these theoretical insights, the paper substantiates the superior performance of CNNs compared to FCNs, providing further support for their efficacy.", "weaknesses": "1. This paper primarily concentrates on exploring the expressive power of Convolutional Neural Networks (CNNs) and argues that a CNN with a depth on the order of $\\log d$ possesses the capacity to learn spatial information within the data. However, it lacks the convergence and generalization analysis, i.e., whether CNNs with a layer depth in the order of $\\log d$ can effectively learn spatial information using SGD-based algorithms remains uncertain.\n\n2. This paper lacks empirical experiments, particularly those using real data, to provide concrete evidence in support of its theoretical findings.\n\n3. Recent observations suggest that Transformers are more efficient in learning spatial information compared to CNNs, and CNNs are not as widely utilized in current practices. In light of these trends, it would be valuable for the paper to offer insights or considerations pertaining to the Transformer model, further exploring its strengths and potential advantages in learning spatial information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and questions. The following is our response. \n\n**1. Weakness.**\n\n-  **Lack generalization analysis.**  We  already provided generalization analysis in Section 4 for learning sparse functions and Section 5 for disentangling the inductive biases of weight sharing and locality.  \n- **Lack optimization analysis.** In our view, both approximation and generalization analyses offer significant insights into the understanding of deep CNNs. The analysis of optimization presents greater challenges due to the non-convex nature of neural networks. At present, even for basic two-layer neural networks, the optimization results are notably limited, let alone for deep CNNs.\n- **Lack empirical experiments.** We have carried out experiments to validate our theory, and the results can be found in the attached **one-page PDF** file within the global response. These experimental results align with our theoretical predictions. For more details, please refer to the **Global  Response**.\n- **Transformers.**\nWe respectfully disagree with the assertion that ``transformers are more efficient at learning spatial information compared to CNNs and that CNNs are not prevalent in current practices''. Firstly, while vision transformers (ViTs) might outperform CNNs when vast amounts of data are available, CNNs tend to perform better in limited data scenarios. This implies that ViTs are not necessarily more efficient, as they require more data for optimal performance. Secondly, in practical applications, CNNs remain widely adopted because of their efficiency with smaller datasets. Even in situations with extensive data, U-net styled CNNs continue to be the dominant choice in diffusion models for image generalization. However, we concur that comprehending why ViTs can better capture spatial information in the large data regime is a crucial question, which we leave to future work.\n\n\n\n\n\n\n **2. Questions.**\n\n- (Q1)  That two-layer ReLU network can approximate any continuous functions has been proved in e.g.,  [Leshno et al., 1993].. \n\n-  (Q2) **Notations in Assumption 1.** The notations are defined in Subsection 2.1 and the weight matrix $W\\in \\mathbb{R}^{C_1\\times C_0\\times 4d}$, where  $C_1,C_0$ represent the output and input channels, respectively. The term $4d$ denotes the input dimensions. Note that in this paper, $C_0$ is set to be $1$. \nAs such,  $W_{j,1,k}$ denotes the weight  connecting the $k$-th coordinate to the $j$-th output channel.  \nOur assumption regarding initialization is mild and is satisfied by most commonly-used initializations: Initializing each element in $W$ independently from the same distribution. \n\n-  (Q3) **Technical Novelty.** We will add a paragraph to summarize the technical novelty in the next version of our paper. Briefly speaking, it can be summarized as follows\n   - **Efficient variable selection.** We are the first to demonstrate that deep CNNs are capable of executing variable selection using merely $\\log d$ parameters. This  result is derived through a novel *binary decomposition* of indices. \n   - **Tighter covering number bounds.** To the best of our knowledge, our covering number bound for deep CNNs is tighter than previous works like [Long and Sedghi, 2020].\n    - **Fano's method for random estimators.** The lower bounds for LCNs and FCNs are established using  Fano's method from minimax theory [Wainwright, 2019, Section 15]. However, different from the traditional statistical setup where the estimator is deterministic, the estimators produced by stochastic optimizers  are random. To address this issue, *we develop a variant of Fano's method for random estimators*, which might be of independent interest.\nFurther details can be found in  Appendix B.3.o original.\n\n\n**Reference**\n\nLeshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. (1993). Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):861–867.\n"}, {"review_id": "oP4TghP6AR", "reviewer": "Reviewer_eXvS", "summary": "The authors study inductive biases in deep CNNs. They analyse approximation abilities of these networks and compare the learning performances of CNNs for regression with those of locally-connected networks (LCNs) and fully-connected networks. They show that CNNs of depth O(\\log d) is sufficient for achieving universality. They also present some analysis for CNNs in approximating functions with sparse variable structures. \n", "questions": "The number of channels for CNNs is often large, but it does not increase exponentially. Can the authors derive a universality result with polynomially increasing channels? ", "limitations": "The CNNs with exponentially increasing channels might be restrictive. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The result that CNNs of depth O(\\log d) with exponentially increasing channels is sufficient for achieving universality is very interesting. It shows the power of CNNs and channels in approximating functions. The example presented in Proposition 3.2 about the lower bound for the universality is nice. The comparison between CNNs and LCNs on learning with bounds O(\\log^2 d) and \\Omega (d) is simulating. Though the methods used by the authors are not new, the obtained results are valuable and insightful and can be used to explain the efficiency of deep learning algorithms induced by structures of deep neural networks. \n\nAnalysing structured deep neural networks in approximating and learning functions with sparse variable structures is an important topic in deep learning theory. ", "weaknesses": "The topic of analysing structured deep neural networks in approximating and learning functions with sparse variable structures has been studied in the community of deep learning theory. the related literature should be mentioned in the paper. The work of Mhaskar and Poggio (Analysis and Applications 2016) with fully connected neural networks is based on a known sparse variable structure while the recent work of Mao, Shi, and Zhou (Analysis and Applications 2023) with CNNs is for unknown sparse variable structures. Another paper of Chui, Lin, Zhang, and Zhou (IEEE NNLS 2020) is about learning of spatially sparse functions. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging and constructive comments. In the following, we address the specific questions. \n\n**1. Related Works.** [W1] \n\nWe thank you for pointing out these references.  [Mao et al., 2023] considered various kinds of spatially sparse functions. [Chui et al., 2019]  used deep ReLU FCNs, not deep CNNs. [Poggio et al., 2017]   focuses on studying how deep locally-connected networks can learn functions with similar hierarchical structures efficiently, while shallow fully-connected networks cannot. These works are definitely related, though the settings and analyses are different from ours. In the next version of our paper, we will carefully discuss these related works \n\n **2. Channel Numbers.** [Q1]\n\nIndeed, our current proof requires an exponential growth of channel numbers. However, we do not view this as a limitation since with only $L=\\log d$ layers, the number of channels and the total number of parameters of all except the last layer are only $O(d)$, scaling linearly with input dimension. \n"}, {"review_id": "5tQm2pKw7A", "reviewer": "Reviewer_o2NN", "summary": "The paper theoretically analyses the sample complexity of CNNs as compared to fully connected networks. The authors find that while fully connected networks require quadratic samples with input dimension, the local connections of CNNs reduce the sample complexity to linear, while weight sharing further reduces sample complexity to logarithmic.", "questions": "Is this the first work to provide theoretical sample complexity bounds for CNNs vs LCNs vs FCNs?\n\nAre the asymptotic sample complexities found by the authors practically relevant? Can the authors empirically demonstrate these trends?", "limitations": "Limitations are adequately addressed; the authors clearly state the assumptions of their theory. No negative potential societal impacts.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "**Originality**\n\nAs the authors point out, separating the impact of local connections vs weight sharing in CNNs is not a new idea; nevertheless, as far as I am aware, no previous works have shown theoretical sample complexity results for CNNs vs LCNs vs FCNs.\n\n**Quality**\n\nTechnically speaking, the paper appears solid. The results and proof look correct as far as I can tell. The appendix is quite comprehensive.\n\n**Clarity**\n\nThe paper is generally well-written. The notation is appropriately introduced and concepts are adequately explained.\n\n**Significance**\n\nI think this paper may be significant to the specific subfield that studies the sample complexity of specific model architectures.", "weaknesses": "Overall, I'm unfortunately not too convinced about the significance of this work given that there is already work analyzing at least empirically the sample complexity benefit of weight sharing vs locality (Xiao & Pennington 2022 as the authors point out, but also Poggio et al. 2016). Certainly, it seems that the theoretical result proved by the authors is new. On the other hand, it would benefit the paper to validate these theoretical results with experimental evidence, or at least point to prior experiments that line up with the authors' theory.\n\n\nMinor comment: Using similar-looking notation for orthogonal groups and big O is not ideal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging and constructive comments. In the following, we address the specific questions.\n\n**1. Experimental evidences** [W1, Q2]\n\nFirst, we have conducted  numerical experiments and the results align well with our theoretical predictions. We refer to the **Global Response** and the attached **one-page PDF** for more details. \n\nSecondly, though there are empirical works analyzing the sample complexity benefits by weight sharing and locality, but rigorous theoretical analysis is lacking. Our work fills this gap to some extent.\n\nIn addition, we shall emphasize that the theoretical findings presented in Sections 3 and 4 are also novel and important for understanding deep CNNs:\n - In Section 3, we originally establish the universality of deep CNNs with a depth of $L=O(\\log d)$. Our proof reveals a mechanism of how the synergy between multichanneling and downsampling is crucial for achieving universality. \n-  In Section 4, we demonstrate, **for the first time**, that deep CNNs can efficiently capture long-range sparse interactions. This claim is further corroborated by supplementary experiments provided in the Global Response. Such findings prompt a rethinking of the common assertion that CNNs struggle to capture long-range interactions.\n\n\n\n**2. Novelty.** [Q1]\n\nTo the best of our knowledge, our work does provide the first theoretical sample complexity separation result comparing CNNs, LCNs, and FCNs.\n"}]

Author rebuttal:
**Global Response to All Reviewers**

We thank all reviewers for their constructive feedback. In our forthcoming revision, we will integrate these comments, paying special attention to an enriched discussion on the related works suggsted  by the reviewers, in particular [Poggio et al., 2017].

In addition, we have conducted some numerical experiments and the results can be founded in the attached one-page PDF file:

-  In Figure 1, we empirically show that CNNs with limited channels can learn sparse interactions efficiently regardless of whether they are short- or long-range, without the need of explicit regularization. This is consistent with our theoretical predictions in Section 4. 
In contrast, FCNs and linear regression fail in learning the sparse functions.  
-  In Figure 2, we plot how the sample complexity scales with input dimension for CNNs and FCNs for learning a quadratic target, similar to what is considered in our theoretical analysis. Again, these empirical results are in line with our theoretical predictions in Section 5.

The above results demonstrate that our theory is empirically relevant in the sense that commonly-used optimizers can find those solutions.

Meta-review: This paper studies the inductive bias of deep convolutional neural networks (CNNs) in three distinct ways by giving sample complexity bounds. All reviewers belive this paper makes valid contributions to the community. The AC agrees and recommends acceptance.
Decision: Accept (poster)