Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs
Authors: Aakash Lahoti
Stefani Karp
Ezra Winston
Aarti Singh
Yuanzhi Li
Venue: ICLR 2024 spotlight (2024)
Keywords: Deep Learning Theory
Sample Complexity
Convolutional Neural Networks
Primary area: learning theory
TL;DR: Sample complexity separation between fully connected, locally connected and convolutional neural networks on an image-like task

Abstract: Vision tasks are characterized by the properties of locality and translation invariance. 
    The superior performance of convolutional neural networks (CNNs) on these tasks is widely attributed to the inductive bias of locality and weight sharing baked into their architecture.
    Existing attempts to quantify the statistical benefits of these biases in CNNs over locally connected convolutional neural networks (LCNs) and fully connected neural networks (FCNs) fall into one of the following categories: either they disregard the optimizer and only provide uniform convergence upper bounds with no separating lower bounds, 
    or they consider simplistic tasks that do not truly mirror the locality and translation invariance as found in real-world vision tasks.
    To address these deficiencies, we introduce the Dynamic Signal Distribution (DSD) classification task that models an image as consisting of $k$ patches, each of dimension $d$, and the label is determined by a $d$-sparse signal vector that can freely appear in any one of the $k$ patches. 
    On this task, for any orthogonally equivariant algorithm like gradient descent, we prove that CNNs require $\tilde{O}(k+d)$ samples, whereas LCNs require $\Omega(kd)$ samples, establishing the statistical advantages of weight sharing in translation invariant tasks. 
    Furthermore, LCNs need $\tilde{O}(k(k+d))$ samples, compared to $\Omega(k^2d)$ samples for FCNs, showcasing the benefits of locality in local tasks.
    Additionally, we develop information theoretic tools for analyzing randomized algorithms, which may be of interest for statistical research.

Published as a conference paper at ICLR 2024
ROLE OF LOCALITY AND WEIGHT SHARING IN IMAGE- BASED TASKS: A SAMPLE COMPLEXITY SEPARATION BETWEEN CNNS, LCNS, AND FCNS
Aakash Lahoti', Stefani Karp4.2, Ezra Winston', Aarti Singh' & Yuanzhi Li¹ Machine Learning Department, Carnegie Mellon University, 'Google Research (alahoti, shkarp, ewinston, aarti, yuanzhil @andrew... cmu, edu
ABSTRACT
Vision tasks are characterized by the properties of locality and translation invariance. The superior performance of convolutional neural networks (CNNs) on these tasks is widely attributed to the inductive bias of locality and weight sharing baked into their architecture. Existing attempts to quantify the statistical benefits of these biases in CNNs over locally connected convolutional neural networks (LCNs) and fully connected neural networks (FCNs) fall into one of the following categories: either they disregard the optimizer and only provide uniform convergence upper bounds with no separating lower bounds, or they consider simplistic tasks that do not truly mirror the locality and translation invariance as found in real- world vision tasks. To address these deficiencies, we introduce the Dynamic Signal Distribution (DSD) classification task that models an image as consisting of patches, each dimension d, and the label is determined by a d-sparse signal vector that freely appear in any one of the l patches. On this task, for any orthogonally equivariant algorithm like gradient descent, we prove that CNNs require Ó(k + d) samples, whereas LCNs require (kkd) samples, establishing the statistical advantages of weight sharing translation invariant tasks. Furthermore, LCNs need Ö(k(k + d)) samples, compared to (2k²dd samples for FCNs, showcasing the benefits of locality in local tasks. Additionally, we develop information theoretic tools for analyzing randomized algorithms, which may be of interest for statistical research.
INTRODUCTION
Convolutional Neural Networks (CNNs) exhibit state-of-the-an performance across computer vision tasks, including Image Classification, Object Detection, and Out of Distribution Detection (Liu et al. : Wang et al. (002)). This efficacy is commonly attributed to the biases of locality and weight sharing encoded into CNNs short convolutions. The rationale is that these biases align with the properties of vision tasks, where local and mobile signals determine the output (Gens & Domingos 2014); |Maruu (2018)) In contrast, Locally Connected Neural Networks (LCNs) encode only locality, while Fully Connected Neural Networks (FCNs) encode neither locality nor weight sharing, thus resulting in a larger sample complexity compared CNNs.
(2022): et al. (202);;
Previous works have attempted to quantify the statistical benefit of these architectural biases in CNNs. For example, Vardi et al. al. (2022), Du et al. (2018) and Long & Sedghi| 2020) derived Empirical Risk Minimization (ERM) bounds for CNNs which are tighter than that for FCNs. However, they do not provide separating lower bounds for FCNs on the same task, and cannot rule out the possibility that FCNs can adaptively yield better bounds when the input satisfies locality and translation invariance. In fact, as noted in Li et al. 2001)) without taking the training algorithm into consideration, standard lower bound techniques cannot be used to show a separation between the three models. This is because an algorithm can simulate CNNs and LCNs within FCNs. Thus, if the algorithm is unconstrained, the minimax lower bound for FCNs cannot be greater than any upper bound for CNNs or LCNs.

---

Published as a conference paper at ICLR 2024
From the Cats Dataset Zhang al. (2008). The cat, which is the class-determining signal, varies in position across images, showing the translation property amidst background noise.
Figure 1:
Recently, Li et al. (202T) established sample complexity separation between CNNs and FCNs that were trained on the restricted class of equivariant algorithms like gradient descent Wang Wu (023)) further extended this line of work to show a separation between FCNs, LCNs and CNNs. However, the data models employed in these works are not truly reflective of the locality and translation invariance of vision tasks. Typically in such tasks, the output is determined by some local pattern, also known "signal". For example, cat within images labeled "cat". Often, this signal is embedded within uninformative background, also known as "noise", and can freely translate within the image, i.e. it can appear in any patch within the image, without changing the label (as illustrated in figure I In contrast, in both Li et al. (202I) and Wang & Wu (2023), the data model considered is as follows: the input (O, Iad), and the label given by f(x), and g(æ) respectively,
2d
4d
2d
f(x)
2
9(x)
22
2 O
Σ f=d+1
22.
22241)
(1)
2=2d+1
Both of these data models fail to capture the aforementioned desiderata of model for a vision task. Additionally, they lack the requisite structure to demonstrate how sample complexity varies with the "'eggre" of locality and translation invariance within the input, or establish conditions on the input under which the differences between CNNs, LCNs, and FCNs are more pronounced.
Furthermore, is worth noting that the driving force for their separation results is the interaction between two halves of the input. Specifically, their lower bound selects "hard instances" from the class of functions H = {x i:d U22+112a), where is a dl x orthonormal matrix, learning which results in lower bound of (dd)). While the interaction between the patches is an interesting phenomenon, it is not the primary characteristic of locality and translation invariance found in images.
We introduce the Dynamic Signal Distribution (DSD) task, which is inspired by the setting in Karp et al. (2021), as our data model for vision tasks. The input æ E Rddd is comprised of k: consecutive patches, each of dimension d. From amongst these l patches, one of them is randomly filled with noisy signed signal. The remaining patches are filled with isotropic Gaussian noise of variance o². The binary label is set as the sign of the signal, so that all images with the same signal in any one of the patches have the same label. By encapsulating concepts of signal. noise, locality, and translation invariance, the DSD task offers a higher fidelity the complexities found in real-world vision tasks.
On this task, we establish a sample complexity separation of ((o2k²d) vs Ö(o²k(k + d)) samples between FCNs and LCNs, as well a separation ((o2kd) vs ((o²(k+d)) samples between LCNs and CNNs. Our analysis indicates that due to no architectural biases, FCNs incur a multiplicative cost factor of i: for each of the two reasons: identifying the location of the patches, and learning the signal vector for each patch. The factor of d arises due to learning the signal which is d dimensional. For LCNs, we can eliminate the cost for identification of the patches since the location of all the patches is baked into the architecture. Finally for CNNs both these costs removed as the architecture not only localizes all the patches, it also allows the signal to be jointly learnt across all patches via weight sharing. It is noteworthy that both the LCN and the CNN upper bound feature k + d factor instead of the expected factor of d. This is an artifact of the gradient descent analysis, and is suggestive of being potential cost for the algorithmic efficiency of gradient descent.
Formally, equivariance is defined on the pair of the network architecture and the training algorithm. For brevity, we may refer an algorithm as equivariant, when the underlying network(s) are clear from the context.
2

---

Published as a conference paper at ICLR 2024
Our approach diverges from Li et al. (2021); Wang & Wu (2023), because in our task, the marginal over the imput is not a O- O-mean Gaussian, but a mixture of Gaussians, which is not an orthogonally invariant distribution. As consequence, for deriving lower bounds, we cannot apply the Benedek- Itai bound from Benedek & Itai 1991) as done in et al. (202T), nor can we directly use Fano's Theorem as done in Wang & Wu (2023) owing the absence of the semi-metricness of l2 loss under an invariant distribution, and analyzing the expected risk under a mixture of Gaussians is analytically difficult. Instead, we utilize a novel technique that leverages the randomness of the training algorithm to break the original minimax argument. In case of FCNs, we prove sample complexity lower bounds for the is the simpler problems using a novel boosting technique to derive reduction to the Gaussian mean estimation problem on the unit sphere. To prove sample complexity lower bounds for the simpler problems in the case of LCNs, we prove variant of Fano's 's Theorem that can be used for randomized algorithms. Distinctively, our variant does not require the semi-metric property to hold on the entire space of output functions, as is needed in the "Fano's Theorem for Random Estimators" developed in Wang & Wu (2023).
bound problem into k simpler problems using simulation-style
Our sample complexity upper bounds depend on the analysis of an equivariant gradient descent style algorithm LCNs and CNNs. This is unlike the separation proved in Wang & Wu (023). where they use covering number- number-based arguments for ERM analysis. The advantage of doing a gradient descent analysis over ERM analysis is two fold: First, it demonstrates sample complexity separation for computationally-efiiii because while a separation may exist for computationally inefficient algorithms, the separation might disappear under constraints of computational efficiency. Second, for a valid separation, it is important to ensure that both the upper and lower bounds are derived for equivariant algorithms since non- equivariant algorithms could potentially be more sample-efficentt than their equivariant counterparts. Furthermore, our approach differs significantly from Karp et al. (202T). which analyzes population gradients by assuming enough (poly (k:, d)) samples at each iteration to yield representational gap between CNNs and CNTKs (Convolutional Neural Tangent Kernels). Since we are interested in sample complexity separation, adopt more direct analysis of empirical gradients.
(poly time) equivariant algorithms. This distinction is crucial
2 OTHER RELATED WORKS
We already discussed some of the most relevant works, including Li et al. (2021 y Wang & Wu (2023) : Karp et al. (202T) Vardi al. (202)) in the introduction. Here, we will highlight a couple of additional works.
Another work, Malach & Shalev-Shwartz (020)) proved a computational separation between FCNs and CNNs on a "k-pattern" classification task. In the task, the inputs are from the hypercube {-1, 1)", and the label based on a set of k consecutive coordinates. They employ random-feature analysis to establish that CNNs, with 2 hidden nodes, can learn this task in O(25n) samples. In contrast, we only require (k) nodes and samples. Furthermore, they do not provide lower bounds for FCNs, and instead argue that the gradient is too small for a finite precision machine. Additionally, since their task does not encode translation invariance, they cannot prove a separation between LCNS and CNNs.
NOTATION
Vector and Matrix Notation: We use bold lowercase letters, such as J, to represent vectors, and bold uppercase letters, such as U, V, to represent matrices. Let [n] denote the set {I...., n.). We denote the standard basis of Rº by B, and the individual basis vectors by e, We define the function idx,; : B, -> [r).. (dx,(e:) = 7, for all E [n]. For any æ, indexed from 1, we use x æ/ E IR--i+1 to represent slice from its i-th its j-th entry. For set {x; ) the sequential length-wise concatenation of the vectors, and (x ..; xx, to denote the sequential row-wise stacking of the vector transposes into a matrix. Conversely, for any x constructed via (:) or (.) notation, we denote its 7th component vector by (+) We use U
employ (xI....,, 2x, ) to denote
(ook(((U,,)) U,)) to be the matrix having diagonal blocks of U,'s in-sequence, with other entries set to zero Conversely, for any U constructed via Block(-), we denote its 7th component matrix by U((). The Euclidean norm for vectors and the spectral norm for matrices are both denoted by ||-I|-
Group Notation:
Let 24, and U2 be any two subgroups of GL(n, Then, we define then binary operation x such that Wi * U2 = {U, U, U, E Uh Ul2, n E NJ. It is easy to see that Un * 212
3

---

Published as a conference paper at ICLR 2024
is also a subgroup of GL(n, R). We denote (n) to be the group of orthonormal matrices R and Op(n) be the group permutation matrices on R"x".
Task Notation: Let X S RP, and y S R denote the input and output space of a dimensional problem. Let P be any distribution over (X, and T: X + X' be any function, then we define the distribution P over (X,)) by sampling (æ, v) P and returning (r(æ). y). Let P be set of distributions over (A', )) then we define the set T o P = {r o P P). Alternatively, let 7 be a of functions from X' X, then we define T P {T; o IT ET.
Model Notation: We denote a parametric model by M and its parameter set by W. The model along with its parameter function from X' to IR. Specifically, V'w W, M[w] X R.
We will use O(),, 2()), and ())) as the Big-O, Big-Omega, and Big- Big-Thett notation respectively. The notation (()), (2)), and (-)) hides logarithmic factors.
4
OUR SETTING
We introduce the Dynamic Signal Distribution, an image-like task which is inspired from Karp et al. We also specify the FCN, LCN, and CNN architectures that we consider for our analysis.
(02TT).
4.1 DYNAMIC SIGNAL DISTRIBUTION (DSD)
In many based tasks, the output often relies on local "signal" in the image, a property referred to as locality. Often, this signal is enveloped in random noise, and satisfies translation invariance, that its movement within the image does not alter the output. The DSD task is designed to capture the both locality and translation invariance properties into an analyzable task.
We define the input space as X' R.dd and the output space as y R. Any input vector æ E X' is structured as (x(1),.. ..., (*)), with each (+( being vector in Rd, and representing the 2th patch of æ. Thus, each input consists of & consecutive patches of dimension d. To model the local signal, we employ an unknown unit vector w* E R.d. with ||w"||
To include translation invariance in the task, this signal w" can reside within any one of the & patch locations, described above. Specifically, for each in [k), we define d-sparse mean vector μ4; IR. &R such that pul(i 1)d + id] wr and all its other entries are zero. The noise is chosen to be isotropic Gaussian, with variance o² E R..
Formally, DSD a distribution over (X, with the generative story: sample the index ~ Unif((::). and the label y ~ that the probability density function (pdf) of DSD is,
Then, sample the input data as ærl url i) N( o Iaa). Observe
p( v)
2k(2 2
exp
| 1ee-vA,,
2n
(2)
We also define the Statie Signal Distribution (SSD,), which is the conditional distribution of DSD) when the index parameter is fixed at Specifically, the label is chosen as y ~ Unif( (,, and then input data is sampled as æly ~ NN(y,, Lea). We will use this distribution in proving the lower bounds in theorem 6.1 7.1 by reducing the problem of learning DSD to learning each SSD,,
4.2 NEURAL NETWORK ARCHITECTURES
We now introduce the model architectures that we consider for analysis. We adopt the Local Signal Adaptivity (LSA) activation function, first introduced in Karp et al. ( (2021). l), for all models,
(x(x) IR + R == ReLU(x b) ReLU(-u b).
(3)
where b E R4, is the trainable bias parameter. The rationale for choosing do (x) is its capability to 'filter out" noise below the magnitude of b, while letting signals of magnitude larger than b to propagate through the network. This denoising helps the network learn the signal with fewer samples. We also note that the LSA activation function. also known the "soft- woot-thresholding function" is extensively used in high-dimensinn Since task involves recovering the sparse mean vector, it futher justifies its use for the DSD task.
sparse recovery problems (Section 18.2 Hastic et al. (2009)).
4

---

Published as a conference paper at ICLR 2024
FCN: We consider hiddee---e network with lo hidden nodes. Each hidden node i, is associated with a parameter vector w0 E IRA such that ||2 $ 1. The complete model parameter vector is given by [w,,.. wk, b] E W, where W- W-Rkdd x R. The function form for FCN is,
(r(o X
Φb (w m))
(4)
LCN: Similar to FCN, we consider a one-hicleenlayer network featuring k hidden nodes. The i-th node is associated with the parameter vector E IRd, || S 1. The complete model parameter vector is given by v = [wi..., wk. b], and W = kd x R.,. The function form for LCN is,
Melu[(0): W -
ou(w, (1))
(5)
We consider a one hidden-layer CNN has & hidden nodes. The parameter w E R ||||| < 1 the shared across all nodes. The composite vector [mn, b) is our complete model parameter vector, and W = IRdd x t The function form for CNN is,
CNNs:
Mc(u](>): W + Σ "oww" x00)
The subscripts F, L, and C denotes that the model corresponds FCN, LCN, and CNN respectively.
5
MATHEMATICAL BACKGROUND
5.1 TECHNICAL DEFINITIONS
Definition (Loss Function). We define the loss function for our task as err: (V,3) - R_,
err(g. y) = (īj ( y))
(6)
Definition 2 (Risk), Let F y* and let P be the set of all distributions over (X.Y). Then, we define the risk R: (F,P) + R+ of fumction E F with respect to the distribution P P as,
R(f.P)
E [err(f(x),
(a.N)~
Definition 3 (Algorithm). Let C yx be the sample space that encapsulates all algorithmic randomness, and Ps be some fixed distribution over E. Then, randomized algorithm denoted by 0: ((X, + F, is a function defined from the product space of input data and randomness to the space of possible functions. The randomness is realized by sampling from the distribution Ps.
We may omit (X.Y) and from the notation when they are clear from the context and use the random variable notation On instead, where n denotes the number of samples.
Definition 4 (Iterative (Randomized) Algorithm). Consider a parametric model M, and its parameter set W, such that for any E W, MMw) is maps from the input space X to the oulput space y. Let F [M[[u]] w E W). Let the model parameters be initialized via a distribution
over W. 2 ~ W. Let T be the number of iterations and F (W,S) ST) - W be the update functions for each iteration t. Then the function 0: WWW [F* h() + Fils an iterative algorithm if it adheres to the procedure 7
Definition 5 (Sample Complexity). Let P be distribution over (X,)) and 9,, be randomized algorithu as defined 3 Let 5 ~ pm be n i.i.d. data points sampled from P. For any 5 E [0, 1]. we define the 6-sample complexity 0,, as,
(0g(02 P) = min {n E N [E 5b) REN
(8)
where the expectation is over the input data S", and the algorithmic randomization.
We may omit the distribution from the sample complexity notation n& ns(0n, P) and use the shorthand
n (0,)) instead, when P is clear from the context.
In the proofs. we will employ a generalization of this definition, wherein the parameter W will be replaced by general space =\t and associated fixed, data-independent distribution Ps. =/t includes parameters well other random quantitics. All definitions presented henceforth also hold for this generalization.
5

---

Published as a conference paper at ICLR 2024
Algorithm Iterative Algorithm
Require: Update functions {F") Set of n i.idd data samples S", Parameter initialization w).
1+1
while S do w¹ +- F (w""11 ,
t t ++1+1 end while return w²
5.2 EQUIVARIANT ALGORITHMS
We introduce the concept of equivariant algorithms, originally presented in [i et al. (2021). To keep it concise, we provide a simplified version which is sufficient for our purposes.
To motivate the definition of equivariant algorithms, review the following thought experiment. Consider neural network parameterized as f(Ax, b), where A E Rexp is the parameter of the first linear layer, while b IR9 encapsulates the remaining parameters. We initialize the parameters as (A", 6") and use gradient descent, with learning rate to train the network on the dataset (æ, hn- In parallel, we train another network initialized as (A UT, ,b"). with the dataset {Uz, yi Whe Here, U E (pp) such that A T and A are identically distributed.
Observe that at the first iteration, the output of the first hidden layer for both networks the same, A A'U"Uz xz. This implies that the gradients with respect to the pre-activations of the first layer are also equal. Consequently, the gradients with respect to the matrix parameters satisfy the relation, d loss(A A U ZA"Ur loss A (A == AU". Thus, after the first iteration, the parameter sets ZA
d
for the two neural networks are,
(A' = (A nA,
(A'U", (") = - -A'"",AU", ,b'),
(9)
respectively. By induction, this property is preserved across all iterations t, resulting in the parameters for the two neural networks being (A b¹) and (A (A'"", b³), respectively.
The key idea is that the risk of network parameterized as (A*,b") any data {x, y) is the same as its counterpart with parameters (A LU' bO) on the transformed data {Ux, y}- Now since A UT and A have the same distribution, we can infer that the expected risk of this network trained with gradient descent is invariant to the transformation U of the input distribution. In other words, network learns the original distribution and the transformed distribution equally well. Formally,
Definition 6 (U--equivariant algorithm). Under the notation established in definition 4 let the imput space X C R", the output space y S IR, and the parameter set W C R Let C Opp), then an iterative algorithm On is is U-qquivariant there exists a set V C O()), such that,
1. For all U U, there exists V such that for all E X, and w W. M|w]] (a) M[[ww] (Ux).
2. For all U U. the same V V defined in (1) satisfies Maiyyin (X,3)" W e [7]. and w E W, V (w, (æ,, wihn) F² (Vw, ( (Uv; )n)
3. If w W, then for all V E V. Vw w.
And, equivariant algorithms satisfy the following property,
Lemma 5.1. (Section 4.1 et al. 2021 Of is a U--quivaaiann algorithm, then Vo E X, U Eu,
0(12,, w) (x) 4 (((Uxx,3))
(10)
where the randomness is over initialization.
This property formalizes the conclusion drawn in the thought experiment. That is the performance of an equivariant algorithm when trained on n i.i.d. samples from P1 and tested on Pa would be the same, in distribution, had it been trained on n i.i.d. samples from U Pi and tested U a Pz.

---

Published as a conference paper at ICLR 2024
5.3 MINIMAX FRAMEWORK
We present the minimax framework by closely following the notation established in Duchi (022)) Let P denote set of distributions over (X) and J C y represent set of functions from X' to y. Let 0*: P - FF be some unknown target mapping, and let e = {0 0: (()) E) + F} be set of algorithms with a common distribution Ps over the sample space E that encapsulates randomness. Let p: F x F + R., be some symmetric positive function.
Definition 7 (Minimax Risk). Under the notation from above, we define the minimax risk of learning the set of tasks P using the set of algorithms O as,
2n, (0, P) = inf sup E [pp(,,. (PM).
(11)
B. PEP
For brevity, we may omit P from the notation, when it is clear form context. The primary change in our adaptation of the minimax framework is that allow for randomized algorithms, whose randomness is independent of the input data distribution. In contrast, the original framework is only applicable to deterministic algorithms, typically referred to estimators.
We now present our Fano's Theorem for Randomized Algorithms to lower bound the minimax risk 11 In this variant, we relax the constraint that p semi-metric on the space F. Specifically, given set of "hard problem" instances Py. and their associated target functions Fv, we only require that if a function f E JF is "close enough", in p. any g Fv. then it is "far enough", in p. all Fv \ {g). This relaxation helps prove lower bounds when the stronger metic property does not hold.
Theorem 5.1 (Fano's ' Theorem for Randomized Algorithms). Under the notation established above, let V be an index set of finite cardinality of some chosen subset of P. Then, we define Py = (P. te E V, and Fy == (Px) Yu E V}. For some fixed parameter > 0, let satisfy the condition that, for all fu + fo Fy and f F, p( fu) < 8, then plS, ʃo) > 6. And, for all Pa, P. E Pv.
* v. let the KL divergence satisfy KL(Pu P&) S D for some D > 0. Then,
Wr, (+) 2 5 DD+
In(VV)
The proof of this theorem is presented appendix B
Remark 1. We only need to define p on the subset F x Fv of its domain F F and 0 the subset Py of its domain P to apply the above theorem.
6 FCNS VS LCNS SEPARATION RESULTS
We now present the separation result between FCNs and LCNs, along with an outline of the proof. Specifically, establish that FCNs, when trained with any equivariant algorithm, require l( 2 d) samples to learn DSD upto some constant risk 5. Conversely, there exists an equivariant algorithm that can train LCNs with Ō(o²k(k + d)) samples, to achieve a risk less than 8.
Theorem 6.1 (Sketched). Consider the group V Okd)), then any U-equivariant algorithm that is used to train FCNs, requires 2 22dd) samples to achieve some constant risk 8.
Proof. We justify the choice of 21 = O(dd), in light of the intuition for equivariance presented in section 5.2 Note that the parameter of the first layer of FCNs, A E & is given by (wii...; wx). We establish equivariance if, for every transformation U U. AUT corresponds to valid FCN, and if there exists an initialization such that AUT and A are identically distributed. Indeed, AUT (Uwi;.... UWz), corresponds to a FCN with the parameter vectors Uwn,... Uws. And, if each w, is initialized as un; ~ (O, Ika), then AUT and A share the same distribution.
Our proof proceeds in two steps. First, we establish that learning U o DSD with m samples requires learning & "nearly independent" subtasks, {U o SS with m/k samples each. The underlying rationale of this result is that learning U DSD entails recovering each mean vector {Up4,) JR- Note that these mean vectors are wiir-wise orthogonal, (UH,)² ("Um)) = μ H4 = O. Therefore, even with the knowledge of {Ume hegs, the only information we have about Uμ, is the kd l + 1 ~ kd dimensional subspace in which it lies. Thus, to learn DSD, we have to recover all the means vectors, (Up,) Js, "nearly independently" from each other.
7

---

Published as a conference paper at ICLR 2024
In the second step, we reduce the problem of learning SSD,, into problem of Gaussian mean estimation. For this, we show that if there exists an algorithm that learns SSD,, then we can extract a weakly aligned mean estimate of Uj, from the FCN returned by the algorithm. We propose scheme that reliably boosts this estimate, to generate a strongly aligned mean estimate. This is necessary because standard information theoretic tools do not work with weakly aligned mean estimates. We then bound the sample complexity for any algorithm that is able to return a strongly aligned Gaussian mean estimate using our Fano's Theorem for Randomized Estimators 5.1 m/ (d)) This implies that m = !(okk²d) k2d,, proving the result.
The formal statement of the theorem and its proof can be found in appendix
Theorem 6.2. (Sketched) Consider the groups U1 = [Block (fU1.... Uk)) U, E O(d), and U2 = (U E (kd)) idxkal (Ue(i-1a+11) + ---1 idxia ()) Vi E [M],] j E [d]. Ler U = U1 + U2. Then there exists a e-equivariant algorithm that trains LCNs with Oo²2k(k + d)) samples, to achieve a risk less than
Proof. To justify our choice of U for LCNs, we establish equivariance under 24 and U2 separately. The equivariance under U/ simply follows from an induction on the number of finite combinations of elements of Un Ul2.
Equivariance under 11
Consider an input x E RRdd then any transformation U E U4 operates on x on a per-patch basis. On each patch, U induces, a possibly distinct, orthogonal transformation. We now show equiv- ariance under the notation from section 5.2 The linear layer parameter A E gkxkd is given by w()) which corresponds to a
Block(w)),... w... Observe that, AU LCN with parameter vectors (U(W)),....... w(() And if each w, is sampled as w, ~ NO, Ia). then AU and A share the same distribution.
Equivariance under L12
transformation U E U2 permutes the & input patches amongst each other, while retaining each internal structure of each patch. Let T: [K] - [k]], be the permutation function corresponding to U. Then observe that AUT = (lock(w=<1))----. vectors [w=(1),..... (x And, if w. ~ No Ia), then AU and A share the same distribution.
(x)). which corresponds to a LCN with parameter
Our training uses gradient descent, accompanied by projection the unit ball after every descent step. We included this projection to simplify the analysis, though we note that it can be removed without changing the core proof structure. The training proceeds in two steps. We show that after the first update, each parameter vector achieve an alignment of (w=)TTw ww 12( (k: + d)/kd). In the second step. we use this alignment to reliably filter out the noise patches. while retaining the signal patches. This demoising enables us to prove a stronger 22(1) alignment, which implies that the model has successfully recovered signal vector. Consequently, the model has a small risk S 5.
Detailed theorem statements and proofs are available in appendix
7 LCNS vs CNNS SEPARATION RESULTS
We now present the separation results between LCNs and CNNs, along-with their sketched proofs. Specifically, we show that a LCN trained with any equivariant algorithm, requires (dd samples to learn DSD upto risk of 6. On the other hand, there exists an equivariant algorithm that can train CNNs with ( + d)) samples to achieve a risk that less than
Theorem 7.1. (Sketched) Consider the groups U4 := (Block (!U1...., U+)) | U, E O(d), and U₂ (U E Op(kd) (ddzaa(U((-))a+) + 1 idxxa( (e(z-))+t)) Vi E [K), E [d]. Let u Un Uz. Then any U-equivariant algorithm that is used train LCNs requires 1(02 samples to achieve a risk of 8.
Proof. We have already justified the choice of 24 for LCNs in the sketched proof of theorem 6.2
8

---

Published as a conference paper at ICLR 2024
We follow in the footsteps of the proof of theorem 6.1 First, establish that learning U DSD with m samples requires learning k independent subtasks, {U SSD with m/ samples each. The distinction from the proof of theorem 6.1] is that the subtasks are fully independent. This is because, the group 4 does not permit interaction amongst the k patches. In other words, the vectors {U()) pI..... U(k) } are all d-sparse, and occupy non-overlapping subspaces. Therefore, even we have the knowledge of { {U(() pr we would still have no information about U(1) U00,, have recover all the d-sparse mean vectors independently of each other.
14, Thus, we
In the second step, we prove an citoommation-thoorette lower bound to learn U o SSD, with m/k samples. We find function that lower bounds the risk incurred by a LCN SSD,. This function satisfies the weakened conditions of theorem 5.1 Finally, we use theorem 5.1 together with the Varbert-Varsammov lemma A.1.1 show that m/k (((2dd) d)). And implies that (d)
The complete statement of the theorem with its proof can be found in appendix D.I
Theorem 7.2. (Sketched) Define U1 == {Block ((UI..... U,)) U; = U, U, Odd}, and
U2 := {U E (,(kd) idxxal (eesaa(U(()))-11) + - = idxial (e())))=s), vi [k],j E [d] Let = Ui x U2. Then there exists a U-equivariant algorithm that trains CNNs, as defined in with Ō 2 (l: + d)) samples, to achieve a risk of less than 6.
Proof. To justify choice of U for CNNs, we establish equivariance under Ui and l2 separately. The equivariance under II follows from induction on the number of finite combinations in Un * U2.
Equivariance under 211
Consider an input as RR,dd then any transformation E U4 induces the same orthogonal transfor- mation on every patch of Moreover, it does not allow for any inter-patch interaction. To prove equivariance, observe that the parameter A E &x is given by Block( boock(w,... .. k times .., w). Note that, AUT = Block Block(U
(( = Block Block(U()) W w.... U(4) w.. And the parameter vector, w, is initialized as (O Ia), then AUT and A share the same distribution.
w..... U(w), which corresponds to a
CNN with parameter vectors (U())
Equivariance under U1z
transformation U Uz permutes the ls input patches, while retaining the internal structure of each patch. Equivariance follows directly from the argument in the proof of theorem 6.2
Our approach exactly follows the proof theorem 6.2 We train the CNN using gradient descent, followed by a projection on the unit ball. The training algorithm has two iterations. We show an
alignment of Q (B((( (k + d)/kd) after the first update, and stronger alignment of f2(1) via denoising after the second update. This implies that the model has successfully recovered signal vector, and consequently it has small risk < 6.
Detailed theorem statements and proofs are available in appendix D.2
CONCLUSION AND FUTURE WORK
In this paper, we established sample complexity separation between FCNs, LCNs, and CNNs that are trained using equivariant algorithms on the Dynamic Signal Distribution (DSD) task. Unlike previous works, this task encodes the concepts of signal, noise, locality, and translation invariance, thus incorporating the salient characteristics of vision-based tasks. We quantify the benefits of locality show that FCNs incur an extra multiplicative
and weight sharing the DSD task. Specifically, cost of 2 because they lacks both architectural biases, LCNs incur a & cost because of the absence of weight sharing, whereas CNNs avoid these costs because it exhibits both locality and weight sharing.
In future work, we plan to incorporate second-orde characteristics of images into the data model. For instance, allowing multiple signals to appear across different patches simultaneously would mirror real-world scenarios where multiple objects occur. Additionally, an interesting direction would be to analyze the role of depth in CNN in capturing dependency between different patches.

---

Published as a conference paper at ICLR 2024
REFERENCES
Gyora M. Benedek and Alon Itai. Learnability with respect to fixed distributions. Theor Com-
put. Sci., 86:377-390, 1991. URL https://api: semant icchool cschol ar. wogg//orpsssDDD
33054388
Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples are needed estimate convolutional neural network? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- Saapper__ileeseeeeeeeeeeeeeeesse files/paprrr
ciates, Inc., 2018. URL wttpa//ss//pppeeeee....e.ooeoe/.
John Duchi. Lecture notes for statistics 3tttsaaii engieeeenn 377, 2021. URL httph://tweeet stanford. Baaaaaor..ececllaa///aaaaa//eeee
Stanford University.
Yuxin Fang, Wen Wang, Binhui Xie, Quan Sun, Ledell Wu, Xinggang Wang, Tiejun Huang, Xinlong Wang, and Yue Cao. Eva: Exploring the limits of masked visual representation learning scale, 2022.
Robert Gens and Pedro M. Domingos. Deep symmetry networks. In NIPS, 2014. URL https
7/api www.sttaattttte semanticaccoolar wtt.scccc...accccooooooopaaaaaaa
T. Hastie, R. Tibshirani, and J.H. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics. Springer, 2009. ISBN 9780387848846. URL https: //bokks .orookssgoollo gwoglo.oog..ooooooooooooooooo com boookssiiceeSSaoAAAAA....
Stefani Karp, Ezra Winston, Yuanzhi Li, and Aarti Singh. Local signal adaptivity: Provable feature learning in neural networks beyond kernels. In A. Beygelzimer. Y. Dauphin, Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL net/ /orrm/rrmmm//// jnr
htttps://openrewe
Zhiyuam Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fully-commected nets? In International Conference Learning Representations, 2021. URL
https://openrevii net forum? dowe::/ooooormouuuumueee
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. CoRR, has//200.005545 2022. URL http::t//a......oo////// /bb//
22C1.03545
Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks, 2020.
Eran Malach and Shai Shalev-Shwartz. Computational separation between convolutional and fully- connected networks, 2020.
Gary Marcus. Deep learning: A critical appraisal. CoRR, abs/1801.00633 2018. URL http
Pascal Massart, Jean Picard, and École d' été de probabilités de Saint-Flour Concentration ing.uuuiittiiooiiiquuiiiiiiiii and model selection. 2007. URL
119022238]
Gal Vardi, Ohad Shamir, and Nathan Srebro. The sample complexity of one-hidden-layee neural networks, 2022.
Haoqi Wang, Zhizhong Li, Litong Feng, and Wayne Zhang. Vim: Out-of-distribution with virtual- logit matching, 2022.
Zihao Wang and Lei Wu. Theoretical analysis of inductive biases in deep convolutional networks, 2023.
Weiwei Zhang, Jian Sun, and Xiaoou Tang. Cat head detection how to effectively exploit shape and texture features. In European Conference on Computer Vision, 2008. URL httph:htpssaapa. semant Co.
10

---

Published as a conference paper at ICLR 2024
A RESTATED GILBERT VARSHAMOV BOUND
Theorem A.1 (Msssart et al. (2007) Lemma 4.7). Let {0, 1). be equipped with Hamming distance and given 1 < < N define {0, 1} = {x E {0, 1) 6(0, x) = =D. For every a E (0, 1) and 8 E (0, 1) such that D S o,3N, there exists some subset @ of (0, } with the following properties,
8(0,0) 2(1 a) v(0,0' E 0 0 #
(12)
N
In [ 2 pD ln
(13)
D
where,
P
In(a (- ln(3) + + 1).
(14)
Corollary A.1.1. Let S be the set of all unit vectors of NR,, that is, S {u u E BN ||uu|| = 1}. Then for any constant e 2 N. there exists some subset C S of size in((S) 2 N such that, for all u, U E S, ui'v <
Proof. We set the value of D = N. Consider the set S = { v/D u E 10,1 | D}. It
2.
easy see that S C S. Observe that for any u, v S1, 6(u, > N(1 9) if and only if
TTe < c. Now, we set c 2 and apply Gilbert- Varsshmmv Bound,
In([$]) 2 (cIn(c) c I)N.
(15)

---

Published as a conference paper at ICLR 2024
B PROOF OF THEOREM 5.1
The following helper lemma derives the KL. divergence between two transformations of SSD, namely U SSD, and V o SSD,- Lemma B.1. For any U, V E (kd)), then the KL. Divergence between U o SSD; and V o SSD, is,
KL(U SSD, V SSD,) 1-cos(a)
(16)
0²
where cos(a) (UHr))VV
Proof.
UU
exp
2
KL(U SSD, ||
SSD,) (aSS)~UeSSD
In
(17)
|| y vu+1l
exp
20
11 - y y1u+l
exp
20
In
(18)
#=yUpttoe
a - y V4uel
exp
| Uu+11
exp
2n²
E
E
In
(19)
U14
200 Viu. 112
exp
20
exp T Um2/ exp(x Vp./o²)
E
In
(20)
uoUpctoc
E
LTUUp//O -x x VV////
(21)
Uptttt
UUV''
(22)
1-cosla)
(23)
which proves the required result.
Theorem 5.1 Fano's Theorem for Randomized Algorithms). Under the notation established above, = let be an index set of finite cardinality some chosen subset of P. Then, we define :y (Pa
(0r (P.) Yo V}. For some fixed parameter 8 > 0, let p satisfy the condition that, for all fu + fo E Fv and f E F. if p(f. fu) < 6, then p(f. fe) > 5. And, for all Pu, P. E Pv.
yu E V). and Fy
v. let the KL divergence satisfy KL P.) D for some D >> 0. Then,
Mr, (+) 2 8 (1- "Pttu(2))
Proof. From the definition of minimax risk, (9)
inf sup 8E0 PEP Sm.P" E~P(E)
> inf sup dE@ PEP, 5t PP (p(0(5 <),0 (P)),
E
inf sup
5), (Q))),
6ee QEΩi (S",E)-
where 23 = (Q(S" = (S*) PE(E) P Pv). and we overload the target mapping notation and set 8 - where is the distribution corresponding to Q. First, observe that for all Qn, Q E Q3. u + v, the KL divergence between the two distributions is given by.
KL Q+)
Qu(S"
P Pa(E)
(S [S", Qu(S"
SA~PR
(S())
E (S")
KL PR
PM
kL || P.) n.D.
PF(Sa)
12

---

Published as a conference paper at ICLR 2024
We follow in the footsteps of the proof of Fano's Theorem [Prop 7.3 Duchi (2021)) For any Q 23.
g/ 0 (Q)) 2 K 1 0 (Q)) 2 83 2 8 Plp 0* (Q)) 2 6].
define the testing function, V:: V as,
(f) arg argminnp(f. NEV
where ties be broken arbitrarily and the analysis would still hold. Let be the uniform random variable over V. Recall the assumption on p that, if plS, Qu) < 6, then p(J: Qu) > 6,
sup Pip(On, (Q)) 2 81 QEQş
28 v= vl.
V
(
P (0.)
From the above, 24 and Prop 7.10 and Eq 7.4.5 from Duchi 2021 we have the result,
Wt, (0) 2 8 m2+nn(2
[n([V]
13

---

Published as a conference paper at ICLR 2024
C FCNS VS LCNS SEPARATION RESULTS
C.I FCN SSD LOWER BOUND
Lemma C.1. Let Sth (SSD1)" be i.i.d. data samples drawn from SSD Define the equivariance group U O(dd). Define the subset ú U such that, for all U U, f2..... k), Up ekd-k+t- Let (UoP|U & ú} be the set of problem distributions. Let E be the sample space that encapsulates algorithmic randomness, and Pz be distribution over E. Let θ == {0: (Xth E) 7 3 be the set of U-equivariant randomized algorithms that estimate the mean of the input distribution using i.i.d. samples. If.
inf sup 6, UEu (u
E
10,,
Up1 2 0.25,
(24)
then n = kd), for large enough k. d.
Proof. We will prove this statement using Fano's Theorem for Randomized Algorithms 5.1 that since ||||| is already metric, the relaxed semi-metric property holds for all 8.
Observe
We begin by constructing a 26, 8 = 0.25, packing of the set of means S {Upi IU E 27) Observe from the construction of U/ that,
S C S = {u
u
E
IR
kd
||/|||
= 1, u E Span((e1, , })
= S2 = {u
R kadd-k
||
1},
Sg = {u
R
||||||
1, 1,uli]] : hd
kd-k
S = {u
R
||l|||
= }
where = denotes the fact that S,,8 and S3. S4 are isometric sets under the Euclidean norm. Therefore, it is enough to find 25 packing of S4 to find a 28 packing of Sj. Now, define the set
k Sy {u R 2
||z/|| 1). and observe that (S,, II-II) and (Sa, II-I1) are isometric. Therefore, it is enough to find a 45 packing of Sz.
u²v S J. Therefore, for large enough k, d, by Corollary A.1.I we have that the size (N) of a 25 packing of S satisfies,
Now observe that for any u.u Sg, Iu w|| > 4 * 0.25 =
In(N) 2 0.15kd.
(25)
Note from Lemma B.1. that the KL divergence between any two distinct distributions, P,Q, corre- sponding to the 28 packing satisfies (L(P || Q) S z Applying Fano's Theorem for Randomized Algorithms 5.1 we get,
2R, (e) 2 0.25 (1
n0200+ +ln(2)
(26)
0.15kd
which implies that n = (ilooookkk ku),, completing the proof.
Theorem C.1. Let F denote the class of functions represented by the set of fully connected neural network models, M,[W], as defined in Let 5th (SSD;)" the n i.i.d. data samples drawn from SSD,, with = Ó k),, and k = (exp(d)) Define the equivariance group V = O(kd). Define the subset U C U such that, for all U E ú. t E {2.....k. k.., Upt ekd-kit- Let g E E encapsulate the randomization, and let Ps. Let ④ {0 0: ((X,))" x E) FF be the set of U ---equivariant algorithms, such that bT buii 10-2 then for large enough k. d,
inf sup
E
R (8(S") . U SSD < 8
(27)
PEE Ueu P- sm Sm (USSD,)))
iff n (2 for 8 0.5 x 10-2
Proof. The proof proceeds by reducing the problem of finding fully-connected neural network with a small expected risk to a problem of estimating the unknown mean of a Gaussian distribution. We then use Lemma C.1 to establish the required sample complexity bound.
14

---

Published as a conference paper at ICLR 2024
For brevity, we refer the distribution SSD1 by P. If any algorithm 8, E A achieves the maximum expected risk of 6, then we have,
sup E [R (On, U [oP) s8 Ueu
aU, E
R
0 n
P)] Uo
Uo
<
(28)
Markoy VU,
P
R (On: P) 2 0.5 < 26
(29)
Let the parameter vector of the fully connected neural network (FCN) that is returned by the algorithm 8, be given by = [w...., Wgg b). We define cos(a;) (Up1)² (²pz)"w w. as the alignment between the mean of the U o P distribution and the parameter uz: Then, the following holds:
R P) < 0.5 = 3i [kt. cos(as) 2 b/2.
(30)
We prove this via contradiction. For an i.i.d. data sample (xt, v) ~ Uo P. consider the the push-
forward of the sample yæ through the FCN. If for all i E [k]] cos(a;)
b/2, then the probability
that the for each FCN node, its push-forward is < O, is given by 2 1 - ( mminm /2r) =
where p can be made arbitrarily small for large enough k d. Therefore (v Σ = du T x))² 2 1
with probability 2 1 - p. which results in a contradiction, because the expected risk is S 8.
Mean estimation minimax problem
Consider the following problem: Let P = {U PIU Ui} be the set of distributions. Let m = (n + 1)100/BB Pmin be the number of samples. Let E be the sample space that encapsulates algorithmic randomness, and Ps, be a distribution over Ej. Let θ == (0: ( E1) + ghd-1) be the set of U-equivariant randomized algorithms that estimate the mean of the input distribution using m i.i.d. samples. Then the minimax problem is,
inf sup 8m e
Ueu STH (U'M(U 110m UpAl
E
(31)
We will now propose an l--qqiivariant algorithm 0m for the above problem, that uses the algorithm 0, as subroutine such that it achieves a constant max eтror of 1/4,
E Ueul 5m (UOP) 110m Upi S 1/4.
sup
(32)
Identification procedure
Before we define 6m. we provide method, which given a FCN, can identify (one of) the parameter w; such that co;( 2 bmnin/2 with probability 2 1 p. there exists such a parameter. Otherwise, the method returns nothing, indicating that such parameter does not exist, and this indication is correct with probability 2 1- p. The method is to push-fore forrafr an i.dd, data sample (æ; y) ~ U.P. through the neural network, and return the parameter corresponding to the first node whose output was positive. In the first case, the probability that none of the nodes with cos(a;, 2 bmin have a p.
positive output, any nodes with (a,) < buiia/2 has positive output is < k (-0(-muin/ In the second case, the probability that none of the nodes with cos(a;) < bunin/2 have positive output is also > k-b(-b /20)
p. This concludes the proof.
8, definition and analysis
The algorithm 6.. divides the data into S 1000 b2
min sections, each of size n + 1. In each section, it runs the algorithm On on training samples, and uses the remaining sample to identify the parameter w,, such that w Upz1 2 0min/2 using the procedure outlined above. If this procedure returns nothing, then set w. 0. Finally, it projects the sum of these vectors to the unit sphere,
i = 1Σ w.
wr In case, the sum Σ. w. = O, the algorithm returns el.
Analysis: We now show that for all U, Blia Up S 1/4. We begin with the observation that if the identification procedure did not fail, then the random variable w, can be written as,
w. = Ap1 + /1 x²++.
(33)
where X, jut are both random variables, such that À > b, and uf uT m1 = O. We define the kd - 2
dimensional unit sphere S (ulu² " μt 0, ||u||| = 1}. Then, we claim that ut ~ Uniform (S).
To see this, consider two points u, S. Then, there exists U, E U, such that U1p11 p1.
and U, e. Now consider running 0,, on the input data ( (æ,, Dr )m U o P such that at
15

---

Published as a conference paper at ICLR 2024
Instead, if we were run 8m on {UI V4 hm U,U o P, then observe that μi v. Therefore, 2). Also, note that UU1 P = U P. because Gaussian is an equivariant distribution. Therefore, Puluj =u] = Pulu v|. Since U, u, were arbitrary, this proves the claim that f ~ Uniform(S).
Pulmi = u] = FU, ما
Let tt be the number of sections for which w, + 0. By Chernoff bound on the Bernouilli random variable corresponding to the event R (fn, Uo P) 2 0.5, and the Identification procedure analysis,
i 2 /00/ with probability 2 1 e-xepp(-a (esp(-450) -500/ min 1000p/0pmn. min 2 1 - 10-10, Now observe,
11 Emigo vo w,
Σ Em A, + t 1-13 X3
(34)
m
Eiruzn / V1-2uui
Umin + Mi
(35)
mi
N Umin + pi
Σ 10
v X2
cx
(36)
m
|e,1
where E, ~ (O, IRa) By the concentration of Gaussian norm, 0.5v S ||E 2vkd, for all 8.
with probability 2 1 10-10, 10, for large enough k, d.
E Ew w. i
bmin + p1
Σ 12
V1
X2 2
(37)
|c,1
bmin +
1
Σ
v
X2
(38)
Teal
w,50
Imin
+
V
0.996
(39)
m
[c.1
F0
with probability 2 1 - 111-0-19 10-10, for large enough k d, using the Gaussian CDF Also, we analyze,
Σ
w.l || 1
Em A + A
(40)
m
Ew, V- ||E1,
bain
(41)
Ew, 2 2111-// Vkd m
< duin
(42)
bmin
S Umin + 0.4bmii & 1.4bmin-
(43)
Vid /m
Combining the dot-porduct and norm analyses, ji p1 2 0.7 with probability 2 1 - 10-9. Therefore the expected risk of ém is,
E E Upill S 2 - 10 s 1/4
(44)
Using Lemma we have that,
100
(n 1) (((okk(())kd)) = n ===044 (ooopdd)).
(45)
8 min
Theorem 6.1
(Formal). Let F denote the class functions represented by the set of fully connected neural network models, My as defined in 4 Let S ~ (DSD)" be the n i.i.d. data samples drawn from DSD, with Ō( and & O (exp(d)). Define the equivariance group U O(kd), let (F')r be set of update functions, and let the model parameters be initialized as w ~ W, for some distribution W. If the algorithm, (S*, w. MM ( (Ferr), is -equivvarian,,, such that bT > bmin then for large enough k d,
ns(00)) max(S (o² .40k).
(46)
where 5 =0.25 1 bmin 10-2
16

---

Published as a conference paper at ICLR 2024
Proof. For simplicity refer to the distribution DSD by P. and the distribution SSD, by Qu for t EE kk.. Since the algorithm 8n is U--quivarran,, lemma 5.1 gives us that for all E U,
(1 = (({Ux; Bi (Ux))
(47)
enr (i( A em (0((Ux;, vi (Ux)))))
(48)
E
enr (i Sm~P" (a.y)
E
E er (0( (i
(49)
8 pm (w
R (0,, P)] = Sr~(UoPIp 9
R (on P)P
(50)
E
R (On, U Uo Q,)],
(51)
(U>(U e k
E (PPP)"
[R (0n. U Uo Q.)]
(52)
To simplify 52, we begin by showing that the expected risk incurred by the algorithm is the same for every distribution U Qi Specifically, for all i, [k],
E UPP)"
E [R (B,, U Q:)] SU>(UPP)
[R,, U o Q,)]
(53)
For i = j. the 53 trivially holds. So
assume that * From the definition of DSD, note that for any a, 8 E KK, we have that HT UB = 1aa = 3). Consequently, for any U E 24, we observe that, (Upa)) Ups = U = u = 1aa= 3
(54)
The above fact ensures that for all U E U4 there exists a U, E U, such that for all a E [K {i,j}. U₁ UHa = Upa and that Up, Upy and U,UH, Un, In other words, the map U1 swaps the vectors Up, and Ups. and keeps the other vectors unchanged. We again use the U-equivariance of d, to infer from lemma 5.1 that,
((U (UIx)
(55)
err (0(f2; (.))) v) em (0((U, 2. (U,
(56)
E SUoPUo UoQ.
[err (0(1)))))))))
E Sue UaQ.
E
(err(0(11)a)) vihn)
(U1z). (57)
[err (0((2), (()) S">((Uo)) UeQ,
E UoP)) U,UoQ,
[err (1,,
(x),
(58)
From construction of U1. we know that U,U o P Uo and
U UoQ U,
E E 9" (U>P" UoQ.
err (0(( y (x) v)] S">(UoP) UcQ
eeir (0(())))))(<))
(59)
[ (0,, Uo [,), S"e(Uu [ (0., U Q:)] Sno(U
(60)
This proves the claim
53
Substituting it back into
52
E Pm
[ (8,.:)]
E ("oP
R (0., U [1)]]
(61)
sup
E
[Rn, U [oQi)]
(62)
Uell (UPP""
where, we define ú C U such that, for all U E U f (
k}, Un end- Let W. P= = W, and θ = {0 0: (2),))" - F) be the set of (kd) equivariant algorithms, such that 6"d bmin- It is easy to note that 0,, E e. Therefore,
R (0n, P)] 2 inf sup E e. Ueil (uPP"
[R (0,, U Q1)),
(63)
Sm
17

---

Published as a conference paper at ICLR 2024
We will now perform a series of reductions to lower bound the above minimax problem. with the minimax problem of learning SSD1. The central concept behind these reductions is to demonstrate that a given minimax problem can be 'simulated" by more tractable one, and thus the tractable problem serves as a lower bound on the original problem.
Let O₁ [ 0: (+),)) U E (kk)) equivariant, and b² 2 bmin- Define the set ún Un ii {Block(U, Ii) U E uj.
F) be the set of algorithms that are Un {Block (U, II)
Define P be the indexed distribution with the generative story: Sample j Unif[k], then sample (æ. y) ~ Qj. and return ((., v). We can then lower bound the minimax expression 63 as,
2 inf sup E 8E81 U,ed w--
E [R ((((((2,))))))) (U,,,)
w). U Q1)
(64)
The inequality follows from the fact that for every 0% E O there exists 6% E 1 that discards the index j and returns the output of 6%
Let ni be the random variable that denotes the number of samples drawn from U1 o P when j
Using Berstein's 's inequality, we get that, I my I == 26
3n with probability 2 c c:= 1 2 exp( 10k
We will refer to the event, 26
n S n I m, as E. Then, we can lower bound 64 as,
2 inf sup 8E91 U, Eth, w- (U.)))))~~ [R (O((
w), U F].
(65)
For the next reduction, we generalize the definition of n,, and define n, to be the random variable corresponding to the number of samples drawn from the distribution U o Qi for all i E [k.] Let y (Unif[]])) be a uniform random vector over (+1,-1, of size nt, and E (Onkkd Inka) be a vector of i...d. standard Gaussian random variables. Let θ₂ {0 0: ((X ))mm x (()= x UNU {0))* (R)" x Rand x W)) - F} be a set of ((kd) equivariant algorithms that take as input the training data, {Up) mean vectors, the number of samples to be drawn from each mean, pre-sampled values of y and e, and the parameter initialization respectively. subsequently returns a function within F. Then we can bound 65 as,
2 inf sup E E E #eea Uel w (m:)) U.e (mm())))))"
E
(0(ST) (e(O(S".((UAAA ((Up)). v, w)), Q1) E
(66)
The last inequality follows from the fact that for every 0% E 1, there exists 6% E O2. that first deterministically creates the indexed dataset using 5th (U {niff y, e and then runs 0g.
For notational brevity, we define E| = (R=d)k-1 x (NU x (R)" x Rundd x W, to encapsulate the randomness in { -U,32. 34 {n y, e, and w. We denote its associated product distribution by Pz. Recall that this distribution must be independent of the input data distribution. To see this, we
recall that from the construction of 21, that for all U E ú, t E f2..... k), Up Ckd-k+t, which are fixed deterministic quantities. Rewriting 66] we get,
c inf sup E. 8EB, Ueu PrPP, (mm(U pm
E
[O(STT :E), U. Qi),
(67)
We have effectively reduced solving the original problem P into solving its constituent problem Q with approximately n/k samples. We have already proven a lower bound for the SSD problem in Theorem 4 Using that result, we have,
Se pm [R (R,, 2 c* 0.5 * 10-2,
(68)
iff (()2kd), which implies that n 2(00222d) Since, c (1 exp( (T))) using n 2 40k, we can bound e 2 (1 2 expp( In(4)) = Therefore,
E pm
[R (On, P)] > 0.25 10
(69)
iff n = 2d)2k2d), proving the result.
18

---

Published as a conference paper at ICLR 2024
C.2
LCN UPPER BOUND
Theorem 6.2 (Formal). Let F denote the class of functions represented by the set of locally connected neural network models Mc. defined in equation Let the input data samples be drawn from the DSD distribution, 5 (DSD)", with
Ō (x)) and k- ((exp(d)) Define the following groups:
21 == (Block (UI,..., U&) U, E O(d), U2 = {U E (p(kd) idxxaa (UNNa((U(()))+41))) +
idxxa( ()))))))))))))))), Vi E [k], Vj E [d]. and U = U1 * Uz. Then, there exist update functions (. and a model parameter initialization distribution W, such that (Mzz, (PeJr, W, W, is U4-quivariant algorithm, and for large enough k, d,
n25( = max(O ( (o²k(d + k) In(kd)) 80k Indd)))
(70)
for 8 O().
Proof: We begin by defining the algorithm 0,, we then establish that 0, is a Ud-equivariant algorithm, and then we analyze each iteration of the algorithm to prove the required sample complexity bound.
1. Algorithm Definition
To define the algorithm 8,, { (Fe) W" we need to specify the initialization distribution W. and the update functions {Fr At iteration t = 0, we initialize the model parameter oo = (wf,.., wff 69] as follows: for each i [k], the vector wo is independently sampled from the distribution (O, 7Ia), where y = 100 and bias is set as 1o = 0. The superscript denotes the iteration number. We define the empirical loss function for N Z+ data samples as,
k
1: (W, -
Σ 9J
Σ
Φ (w:T aT)))
(71)
The algorithm proceeds in T = 2 iterations. For simpler analysis, we split the input dataset S" into two equal sized datasets ST and STh with m == samples each. Then, for each E (1,2),
F1 =
wi - to Ve, ((::sT)) wi
we n. Ve, (w:.77))
b,
(72)
(0.s""
where 1/1 = 1, 12 = k x 103, bj
1 d) ko(
= 10
32
kd
2. Algorithm is Equivariant
To establish that 0₂ is L--qquivariant, we only need show that it is both U1 and -z-equivariant, because, every element in 24 is finite matrix product of elements from Un and Uz. We define groups
V1= (Block( V I..... Va. L) V E (d), i [A:]] where I is the identity matrix of size 1.
1/2 = (Block(U,I.) U E 22), and V = V1 * V2.
To prove 241 equivariance we need to verify the three conditions in Definition 6 For any data sample
æ. y E (X,3), U Ui wn E Rd; [k:. b E RR,, choose V Block( (U U()) I)) E V.
Then, the first property[
[ Tholds as,
Mz(u](a) = Σ (w x (1))
Σ (w (U = (M.)V i=1
(73)
1=1
For each iteration t E [2]. and S (X, the second property 2 follows as,
U U u, UVe,"
Fr (Vo, (Vv,UO.') S*)
(74)
Ut ww (Vo.Uo8T)
I - yi (Vo.:UoS")) [ (.
b
U w1 -1 W (viss")
Uik) (w -n V V.y ((::sT))
be
(75)
U m. V [(=:S")))]|
( w m ((v:ST))
U0l) [w n V ((,
u (w - V و ((v:)()))
(76)
|00 -o th ((:35)
Ii 75 V. [(r.ST')]
V., SM)
(77)
19

---

Published as a conference paper at ICLR 2024
And property 3 can be affirmed by observing that, for all V E V1,
Ve
[0 wi
W b%,
(78)
- [ w b9 =
(79)
This proves that 8, is U1 -equivariai. We now establish equ-qvviaaiiance Observe that action of any matrix U E U2 is to permute the k patches of the input. Let :: [k] + [k] be the permutation function
corresponding U. For this given U, we choose V Block ( I1) V. For any æ, y E (2) w, E R i E
[k]] b E R+, property of equivariance holds as,
Mc(o](x) = Σ =
2bww, (0)) = Σ Ss ós (()))) (1)) MM(Vel(Uz) i=1
(80)
For each iteration E (2), and 5 E (2, the second property
follows as,
w.1 an (Vv: ||- - V (1) (e:
Fe (VV, UO5"))
(81)
(. 7o V - (Ve:Uns;T)
be
W To (Ve:UnSTT)
wi W. ((v:S")
V (U
bp
(82)
w - Vi, (0
w
VF (t.
(83)
And finally property 3 can be shown by observing that, for all V E V2,
Vo"
0 (k)) b%], [w]. 0 b0]= =u. v.
wm 0
(84)
(11)
(85)
Thus, the algorithm 6, is -qquiivaari,, and therefore is z/-qqiivari.
Algorithm Analysis
We analyze each iteration of on, with n = max(2o*k<k= + d) In(kd), 80K In(kd) samples, and establish that 0, achieve expected risk of at most 5 2.5 x 10-3 Since k = (cxp(d)) and Ō we assume that vd 20 (k)) and 100 1100/I1ni In(dd) < 1.
The outline of the analysis is as follows: We show that after the first update step, we reliably recover
the unknown signal vector, upto an aligmment of M b+dd). In the second step, we show that this alignment is enough to threshold out the "noise" patches while only letting the "signal" patch pass through the first hidden layer. This enables us to recover the signal upto an alignment of 12(1), which results in the expected risk of the learned LCN being smaller than 6.
3a. Update Step
For each E [bt], we denote w = wp V
m (ww 0: ST)) to be the unnormalized version of w!!
Thus, the alignment of wo with the signal can be written as, (w,)) w0= alignment, we begin by simplifying V [e
( w
To compute this
10 II
m7
ST:)
y/1
po((no ( 2x (o((
(86)
m
j=1
k
-2
Uj
so (oo(wo Tr(
(87)
k
-2
Σ
Uイ () (1w0)) )
(88)
1=1
1=1
b
-2
Σ
Σ
Ui ( =r!")) (1,,
(89)
==1
1=1
20

---

Published as a conference paper at ICLR 2024
where (x) == de (z)))) and the last equality follows by observing that du is the identity function, and % is the constant function 1. As a shorthand, we define 0j == 1 E. (z x ( and Bay = y Substituting this back into 89
V (w 01: = =2 Σ ayB.y.
(90)
To analyze 90
begin by proving high probability bounds the range of aj, for each [m]] From the initialization procedure described above, we know that 1. _ ycs, where e; is the Gaussian random vector defined as E; ~ NN Ia). And with the input distribution being DSD, we know that
(i) yyTiy ge," (f) for all in [k], where c,") NO, Ia) is also Gaussian random vector,
and rij = 1, if in the j-th data sample the signal patch appears in the i-th patch, and 0 otherwise.
k
0j = 1
By (w:))
D )
(91)
i=1
1
Σ co (
(92)
We can now bound the range of Or as,
1+1 Σ Tip w' +|
Σ
T (6) yoe!
6j
22 21 Σ mig
c w -
(1)
(93)
1=1
We first upper bound max, [w= = 1, we have that ef
Ei=1 Mise 20 S max; hef w+1 Since the norm of the signal is 1, " NO, 1). We can now upper bound max, 1785 w+1 as,
max hE? ? w= S 1 max le w 1 $
(94)
with probability 2 - 1111007 To derive inequality 94 we have used the concentration inequality,
P[max;e[1] c w=1 2 /32 S 10 < 10-
And now we seek to bound max, Et_1 r (1) random vector, PP[max,|ee, 2 v 10 lnk)) s 2kexp( define u. - Therefore,
By the concentration of the norm of the Gaussian
100
100
S 2kk 6
S 10-7, Now,
16
max <e (M))EE [m)]
Σ
(1) T 5 S po(vd+ 10 10 In(k)) ToE
max
Σ f=1
u Te (0)
(95)
jE (m))
1=1
d 1o(Vd 10 In In(k)
max
V Vkeyl,
(96)
JE|m]
where 5j ~ (0, 1). The last equality in distribution follows from the fact the sum of k indepen- dent Gaussian random variables is a Gaussian random variable with variance k. Now, from the concentration inequality, P[maxxe[m] |eyl 2 /32 [nmm)
I m < 10-7. Substituting this above,
max [E[
S yo (voVv+++ 10 In(k)) max /ke,l: Toc E
(97)
jE[m)
w yo kd 32m)(m)
(98)
W
/k v kd 32 In(m) s $
(99)
Substituting 94 and
99 into
93
we can now bound oj. for all j E [m].
+
03
>
8
(100)
IV
(101)
21

---

Published as a conference paper at ICLR 2024
We are now in the position to analyze :i!
. = w - 1/ V u (Loo, 0]: ST"),
(102)
90
+ 2.gB...
(103)
j
0 +
1
2z (Urri + xoe (1)
(104)
j=1
0 w. +
2 2 mgjo
j= E;:
(105)
m
where E; (N Ia). Similarly to C;, we can the concentration of the norm of the Gaussian
random vector to show, P[mmx,/ ||æ:|| - v 2 10/In(+)] I 2k exp( 10(k)(())
16 < 2kh 6 <
10-T. Also note that by using Chernoff and Union bounds, we have
m. 2E S د
Tay S
3m with
2
probability 2 1 2h exp(
100 la(k)) 2 1 - 10 for large enough k. Recall that the aim is to bound
10k
(w))² ('="== ( m0 for all i E [k]. For this, we first prove an upper bound for || ll.
|| ||
||kwo + 2k Ei= Fugl
w
2k V
m
(106)
m
S ||:20 || +
2h E/s Fu
w0 || +
2k
Ei, 11,
(107)
1ol
||:w0
|| +
5k
2
Tiy
w" || +
5ka
2
V
1
(108)
S >
+ 5k
Fiy w س
||
+
5kz
1
||E/ll
(109)
2
Now substituting the facts ||e:|| || S vd and that Σ3
Fig
I
3m
2%
|| || S 7
3ky/d
+
15 + 15ke
(110)
m
<
3v/
15
+ 15a
kd
(111)
2kd
4
a (d++ kc+kk)mmme (kdk3)
15
15
kd
(112)
2kd
(k++) (kc)
S 4
(113)
(k++) Ln(ka]
And similarly, we lower bound
||
||
|kw!
||
>
2k
E11l - 11:20,
-
2h Em Fu w ||,
(114)
m
101
3kgr 2
|6:|| - |1::0
k *m
j T4y w ||,
(115)
3
kd
3 2kd
15
(116)
(k+a)l((ke)
4
V (k+-a) In(Ae2)
kd
(117)
Next, we lower bound k( k(zo,)" y''=".
k(w=))"'" "= = k(w 2 "w* + 2h Em r8a3 (w-)= w + 2h 2h0 V at (e))"
"
(118)
m
2k Mm riyay
2k V== oz (E))T "
= -kyc w== +
(119)
+
3k
Em Fi
ban (E.) T w
(120)
2
m
2/m
Tuuker < "n=
+
3
(E.) T "
(121)
4
2 2 (k++)) ln(ke)
Iv
+
3
(E)) Twu" "ww,
(122)
100k.7
2 [n(kkd)
1
(123)
22

---

Published as a conference paper at ICLR 2024
where the last inequality follows from the bounds, |f and P[maxie(M] se, w'1
le ==w'|
(321m(k)) Im(k)
1 S 4/ S 10-7,
100k
100kd
5y (2
2
And similarly we upper bound 10-7 S
(1o Fot))=" w''
2v 2/I(kk
2 /l((kd)
k(w))) ) "
S 1.
(124)
Therefore, 2 (k+d) (n(kd)
2 (w =T "0- 2 (k+ In(kd)
with probability 2 1 10-6. We can
kd
lid
now express / as \vw0 + +V1 - Xoo where 2/ (k++ and (w=))""" O. 3b. Update Step 2
2 A 2 8V
(k+d) (n(kd)
||00 = 1,
kd
kd
We will now show that the $ the "noise" patches from the "signal" patch. This de-noising effect allows us to achieve a stronger constant alignment of each parameter vector with the signal vector.
(k++d) kd
alignment with the signal vector enables us to filter out
We begin by analyzing the push forward of all the noise in the dataset ST" through the LCN model,
max lo(w )T TT, e /lnkka) [.j
max (w:) "ee, ///,
(125)
ie {m))
In + d) ln(k)),
(126)
4vh (b++ In(kd)
(127)
kd
For inequality [26] we have used the concentration of the maximum of the absolute value of mk i.i.d. Gaussian random variables, Pfmax:.j (ww))² the analysis of the first update step that,
(8) /322n((m))) S (mkjo I 10-7. Recall from
c
2
(k++d) In(kd) kd
2 (w!) "n* 2
(k+ In(kd)
(128)
8 kd
From 127
128 for all j E [m]. and E [k]. we have
(2 + )2) ) V (R++d) In(ded) kd dk++d) In(Aed)
yy (w:) 1TH x3 2 (3 222 (k+d)ln(ka) where, Taj 1,
(
(129)
32 V
y, (w yT 20
(i)
32 v
(k+dd) In(kd)
where, Tiy 0.
(130)
kd
/ (k++)) In(ke) kd
Therefore, with by
we filter out all the noise and let the signal pass through,
32
2 (k+t) ln(kd) kd
Dbn (Us (
T x ;
(1)
2 C
1 16 1
(++d)I(((a))
where, rig. = 1, (131)
kd
Φb (us (w:) )T (1)
0, where, rij 0.
(132)
We will now follow in the footsteps of our analysis of update step 1. We seek prove high probability upper and lower bounds for (w,)Tww Tw" w². We define uē = w V wi ((w! by; ST"),, and therefore (w? TT "
(103)² =0 #
We first evaluate the gradient of the empirical loss function with respect to w,
m
dm ( ) (z))) oh, ((wt))af))))
V " [[w] [[]] STT) m
Vj
(133)
m
Dh. (1) (1)(ww) )z o0 (000)) (1)r)aa())))
(134)
where the last equality follows from
131
and
132 Now, for large enough k d,
2 1 - 8 /
(k+d) In(kd) kd
aay=1
=
Sy (w, [T, 2 1 2/ (k+t)) In(kd) kd
(135)
23

---

Published as a conference paper at ICLR 2024
Substituting the definition of a, and simplifying
134
m
V Ww: 51):
=1
(136)
==1
2rija 2 + oc
(137)
2
w
20 mm j-1 1,
E1
(138)
==1
where é; ~ (,, By Chernoff and Union bounds,
S = Σj= 2j=++1 kmg
3m with
26
2
probability 10-7 Also, we the concentration of the of the Gaussian random vector show, PP max; |||,,|| v z 10 /Ink]] S 2k exp(
100
S 2k S 10-7
16
are now ready to bound (w²) "
(w=2)" w- W
We denote a;
k Di= actiy 2
| ||
1/
2ng w + 112
20
E 1=
72
1/2
2r
w
7/2
m
m
$ 1 + 20,0m
|00 || +
BBru
||εi||, Vmk
&
S 1 10
(2a; +
/oka
|ē:ll
vmn
< 1 + 10
2a; Vo=k(k+d))n(kke ln(k+d) 2
Voka
3
- 1 10 (2a; +103)
for a large enough k d. And the lower bound on (wo " is given by.
(w,)Ta u = (wx!)²
"=* + "rot)TT===
2r (w") )ToT)T""" "v" +12
j-1
(139)
J=1
2rg (w " + 172
1/2
N N(0,1),
(140)
m
2 -1 + 2a; 10
kkk bnck+d) X 103
Voka
(141)
> 1 + (2a
10 10-3)
(142)
where we have used IP[|
Vokoc
2 10 10-3,, with probability S 10-?, Therefore,
V o2 (k+ d) ln(k++d)
( " "
-1+10 20. ") 2 0.96.
(143)
||
1+10 (20,
and this occurs with a probability 2 21 10-6
3c. LCN has Low Risk
We now show that this large constant alignment guarantees low risk. We bound the push forward of the noise through the LCN,
6 in(k)
la max ]e[m]
$ 10
(144)
100 In(kajs
To derive the last inequality, have used the concentration of the maximum of the absolute value of l i.i.d. Gaussian random variables, PP[maxje[] (ww))T egl 2 (/22((k) 2g < 10-6 For this
24

---

Published as a conference paper at ICLR 2024
data sample, let & [k]] be the index of the signal patch, then,
Ob (w) )" (t) 2 0.959, @b
(145)
( = 0, A Vi
(146)
We note that with probability 1 1-3x x 10 6, the risk of the classifier less than (1 0.959)². To bound the risk in the failure case, we note that for any E W.
[
9b (w) x ())) [[(
syw x 10)),,
(147)
1(1 Σ 2o " (1))))),
(148)
(a,y)~~SSD)
B[ Σ @o(o))))) )b(cos(a,) + oef;))
(149)
To evaluate the above expression, we observe that the expectation can be written as,
[[(1- Σ (o(ore))) (c + oe Var((1 [ds(oe))) )s(cos(a;) oe;;))
+ B[(1 Σ )b(o)))) @s(cos(a,) + oc,)))s (150)
Varldb(aces)] + Var (arldo(cos(as)) + [(,z)) + (E(ss(cos(aa)) + =
(151)
itj
$ Σ 0² + (as) ko +1
(152)
Substituting this back,
b 1 < 8: j=1
Bl(y Σ
moww? x (1
1
> 2=
(153)
Therefore, the expected risk of the trained LCN is upper bounded as,
EE R (0,, P)] s (1 0.959)² +6 10 6 <
(154)
25

---

Published as a conference paper at ICLR 2024
D LCN VS CNN SEPARATION RESULTS
D. LCN LOWER BOUND
The following lemma provides a lower bound on the risk of each function in the class of LCNs over the set of transformations of SSD1, made using the group U. The group allows for orthogonal transformations within the patches, and does not allow patches to permute.
Lemma D.I. Let F denote the class of functions represented by the set of locally connected neural network models, Mc[W], as defined in 5 We define U := {Block (UI...., U&) | U; E {dd) Let P be the set of distributions {U SSD U E U.. We define the target function 0" ; P + F as, 0 (U SSD,)
M M[[ ,... U w b'I,, where wn is the signal vector, and bt is some fixed
value in (0, 1)
Let Fp be the codomain of 6". Consider p: (F, Fp) - RR,
(U o SSD))) (1 (1-max(0- ||21 cos((1)) 2
(155)
where cos(a1)
Then, the risk of f E F. on U USDD E P satisfies,
RUJUO ,SD)) 2 pls, (U SSD))).
(156)
Proof. Observe that,
=
E (a.
[(0 fx()))]]]
(157)
h
2
E (m.))~UPP
S (w x))
(158)
k
i=1
27
E c,==Uw*+
Σ
re (w x))
(159)
2
Jensens' 2
Σ po x))
(160)
2,00
2
1
1 [css (l::l/001)))
Eoob (1/w cos(as) + || [[]]]
(161)
E B[cs (1|||)/]))))) w1 cos(a,) + || ||0, [|oee]
(162)
where in 162 we used the fact that since (- (z)( and therefore E[os (1w, (|w:||/e))
0, for
all i # I. For brevity, we define ب = ||w||| cos(an), and ē = ////|oo. Then observe that,
Blos(p + σc) Bfmax (0, م b+ σc)] Fimax(0, -p - b σc)].
(163)
|f[max(0..) p b+ σe]] E [mx -p - b + FE)].
(164)
We begin by evaluating E. [max (0, p - - b - ōc)].
Elmaax(0, fi b+ oe]] = 1/2 Elaa - + σe] + Blja - b + Øel]
(165)
( b) + 1 c exp
2
( - b) [1 1-24
24
(166)
= (n b) (1
اسم + 7/1-
(167)
"The claim and the proof do depend on the chosen value of b*
26

---

Published as a conference paper at ICLR 2024
where 1/1 = /
1 2x
exp
(ح-b)) 2x
Similarly, for the second term, we have,
fi + σc)] (- b) (1 + (+tb) + 72,
E mmmax(00
(168)
-(a+)²²) (-123- 2
where 1/2 = V 2 cxp
Substituting these results back to 164
E O + σc)l = ( - b) (1 (1-9)
-1- 1b (-aa²)
p-b ) + + ( + b) (1- ①b
[+bb
0
)) 1/2-
(169)
Now observe that,
8 El - ōe)] = =- +b
R-b (-
Φ
Ā-b
+
Æーb exp
(-
(ي=b)²
V2no
25
+ b+b
(x+b) b)
T
p++
(a=b) b)
exp
(A+b))
(170)
/2
25
Substituting the expression for D',
El - [e)] = 1-- [(1]=][1]) 0e
8
0
-
(1
(-
0
(171)
= b-
+
ü+b
(172)
If a 0, then the gradient with respect to b is always negative when 6 > O, therefore the maxima of [o + Øe]] occurs at b = O, with the maxima being á S 1. If μ < O, then the gradient is always positive when b > O, therefore the maxima of E, [ov + σc)] occurs ò +oc, with the maxima being 0 < 1. And finally, for ş = 0, (o + ōe)] = < 1, by symmetry. Using these observations with 162 proves the result,
R(J.UO))(( max (|x) cos((n)))))
(173)
L
The next lemma establishes that the lower bound on the risk, defined in Lemma D.I meets the relaxed conditions of our variant of Fano's Theorem [.1
Lemma D.2. Under the notation established in the statement of Lemma D.1 we define the set ú C,, such that for all U + V E U, (U (
< 10-3, and for all U ú, E (2....,k). k).
U(O)=* w0 = Edt. Then, for all U # V ú
plS. 0* (U o P)) < 10 = (V) 10-2.
(174)
w ( w' and cos(3:)
w w() Now,
Proof. Let cos(ar)
w
pl. PJ) < 10-2 = (1 - max(O, || cas())))) < 10-2,
(175)
max(0, [|w cos(an)) 0.9.
(176)
By the triangle inequality, we can get an upper bound on cos(31) as,
22(1 - (3)) v 2(1 0.001) - 2 (os((ss()) )), cos(3:) < - (v(1 - 0.001) - / - 0.9) < 0.7.
(177)
(178)
Therefore, max(0, ||we|| cos(B))) - 0.7, which implies that
(1 - max w. cos(33), 0))² 2 (0.3)² > 1
(179)
In the following lemma, we prove a sample complexity lower bound of ((d2kd) for FCNs on the sub-problem SSD, of DSD.
27

---

Published as a conference paper at ICLR 2024
Lemma D.3. Let F denote the class of functions represented by the set of locally connected neural network models, Mc[W], as defined in Let S" ~ (SSD1)" be the n i.id data samples drawn from SSD1. Consider the group 27 C (kd)), such that all U + V E Ü, (U()) )"(VWW"") < 10-3, k). U0 = Eat- Let & E E encapsulate the randomization, and let Ç ~ Pz. 100(1" is lequivaarint algorithm then, for large enough k, d,
for all U E Ud, E [2....,k]
ni ms(0m)) = (
(180)
where 5 0.5 x 10-2
Proof. We refer to the distribution SSD, by P. Since the algorithm O, is U- equivariant, lemma 5.1 gives us that for all U E ú,
8 (( _ 0((Uz, V4 (n
(181)
err ([(((=,,)))))
(0(, Veln)
(182)
E
E
eT (0(( (x))
E E
err
(183)
(m. m P
5m~pp (a
E
err 0n (x).)))) y)] E
E
E ferr (0.(2).
(184)
8h pm (a.g)
(Tm(UeP)"
(u.
[R (0,, P)]
E (UpPU
R (On. UoP]
(185)
Taking sup on the right-hane hand side,
E
R (On: P)]
sup UpPEMoP
E
[ (On, U P)]
(186)
Pm
An application of corollary A.1.1 gives the bound In((())) 0.99d.
In order apply variant of Fano's Theorem 5.1
the following variables: p = ú o P: Py = ú P; F, E, and P= already defined in the lemma; θ (0 0: ((X)))")
F);
( P)= = M[[U(4)))* u0=", (()) b'],, where U E úi b* is some fixed value in (0, and
p(S.0 PJ) (1 max(0, 0,,11,,, | || cos(a1)))* where U ü, and cos(a)) w U w' Recall
w1
from Lemma B.1 that KL(U o P V o P) <
0.999 J/4
a²
We are now ready apply Fano's Theorem 5.I
using the results from Lemmas D. D.2, and 186
(6n: P)] 8m
sup [ (6,, U P)] UePEÑoP
(187)
inf sup UoPElioP
E [R U P)],
(188)
BE8
10
mlo2++m(2)
(189)
0.99d
From the above, is easy see that with o samples, the algorithm incurs an expected risk greater than ! 10-2, proving the result.
"The claim and the proof do depend the chosen value of b*.
28

---

Published as a conference paper at ICLR 2024
We now present the formal statement and the proof of Theorem 7.1 which establishes the 2( kd) sample complexity lower bound for LCNs when trained on DSD.
Theorem 7.1 (Formal), Let F denote the class of functions represented by the set of locally connected
neural network models, Mc(WW, as defined in 4 Let 5 ~ (DSD)" be the n i.i.d. data samples drawn from DSD. We define the following groups, U1 == (Block (UI,..., Up) U. E (dd), U2 (U E (p(k)) idx (dxx,((Ue()))a-1))) +
idxed (Ue(-1))))) vi E [ [d]). and u = U1 * U12 Let (Fetr be the set of update functions, and let the model parameters be initialized as
w W. If (,,", w"; :M[[.. {Firr) is l--quivvarin algorithm, then, for large enough l.
the sample complexity is given by,
mo(O,) max(Si (o²kd) 40k),
(190)
where 8 0.25 1 2
Proof. For simplicity will refer to the distribution DSD by P. and the distribution SSD, by Qz, for I kk.. Since the algorithm O,, is L--qqiivariant, lemma 5. gives us that for all E U,
(( 0((Ux, M4 (Ux), er (f(fo, (z)))))) err err (0((2,, U1 In) (2)),) 5m
(191)
(192)
E
E
E
E err (0((Ux,, (Ux)),))
(193)
(a.D)
R (0n, P)] Sm
E
E
[ (On. Uo P)].
(194)
E
R (Ons U Qi)]
(195)
K
[R (On, U Q.)]
(196)
k Upp
To simplify 196 we begin by showing that the expected risk incurred by the algorithm is the same for every distribution U a Qi Specifically, for all i, E [k].
E
E [R (0... U. [oQi]] SUoP(
[R Qo
(197)
For j. the result trivially holds. So we assume that i * j. Observe that because of the block structure of U4, Up, E such that, U, Up = Up for all & {i.j}. and U2U,U = Up U, U,U2UU, = Up, Since Ü = U,U, E U and o, is a al/oorthogonally equivariant algorithm, from lemma 5.1
Vi E [k). Therefore 3U, E U1 U2 E U2
(((mi,))))) ((U,,, yi (. err (0(1)) err (Ø(1 U 3; 91 (U
(198)
(199)
E [err (1 ("> UoQ;
E
E Upp UoQ;
E
[err (1U12 hi
(1]x),)) (200)
E
E UeQ.
Jerr (0((2;, (.)))()))))
E S*~(U, U,UaQ
E
(ar(0((z;))) km)
(">(Uo
(I), (201)
From the construction of U, we know that U,U o P d
Uo P. and U o Q _ U Qj-
E (U) UnQ,
E
Terr (0( (a: (x)))))))))))) S" PoP
E
E
Jerr
v) (202)
UnQ;
E R (0n, U Q.)] Sn~(UoPpa
E
R [
U 0,)]
(203)
S
29

---

Published as a conference paper at ICLR 2024
This proves the claim 197 Substituting it back into
196
E Sm
[R (0n. P)]
E SnoP")
R (0n. Uo Qi)];
(204)
E Ueul (UOP)"
sup
[R UoQi))
(205)
where 27 [ U4 is the set of "hard instances" such that, for all U + V E ú. (Vpn) < 10
and for all U E ú, and i E {2...., k). Up, Cdt, Let E = W, P= = W. and e = (0
0: ((x V""" + F}. is easy to note that 0n E O. Therefore,
E SmmPp
[R (On, P)]
inf sup 0, Ueu Sh Sum(U)P)"
E
[R (0,, U Q.)l.
(206)
We will now perform a series of reductions to lower bound the above minimax problem, with the minimax problem of learning SSD, The main idea behind these reductions is to demonstrate that given minimax problem can be 'simulated' by a more tractable one, and thus the tractable problem serves lower bound on the original problem.
Define the set of algorithms, 1 (0 0: 2,))", + F), and let U P be the indexed distribution with the generative story: Sample j ~ kni then sample (x, ~ U o Qj. and then return (j. x,, y). We can then lower bound 206 206 as,
inf sup E 8E81 Ueli w-- (j...)"~(UoPP)
E
[R (O((),,,)) v)", w)) U Qi)]
(207)
The inequality follows from the fact that for every 0g O, there exists 0% 11, that discards the index j and returns the output of 8%
We define n be the random variable that corresponds to the number of samples drawn from U o Q1. Using Berstein's inequality, we get that n I n1 S m = 3n holds with probability 26
2k
2 c = 1 1- 2 exp Tox
We will refer to this event as E. Then we can lower bound 207
2 inf sup E 0 Ueü w- (U.
E
[R x, y)", w), UoQ E].
(208)
For the next reduction, we define n, to be the random variable corresponding to the number of samples drawn from the distribution U Qú, for all i E [k]. Let y (Unif()/))* be uniform random vector over -1} of size n and E ~ ((Okkd Inka) be a vector of i..dd standard Gaussian random variables. Let O2 {0 0: ((X, y x (i be a set of algorithms that take as input the training data, {Un) 22 mean vectors, the number of samples be drawn from each mean, pre-sampled values of y and e, and the parameter initialization
x (N J {0))*
) x (R))" x Runk x W) + F)
respectively. It subsequently returns function within F. Then we can lower bound 208 as,
2 c inf sup E 0E02 Uel w-- (m:)t u.e (m
E E E
[ (0(S"), {UN))2 {n,)i y. w), U U E
(209)
The last inequality follows from the fact that for every 02 E O1, there exists 0z E O2, that first deterministically creates the indexed dataset using S (UH }/2 {n, uk y, E and then runs 6 For notational brevity, we define E = (N U {0))* x (R)" Rukd x W. to encapsulate the randomness in (n: fnalt, y, e, and w. We denote its associated product distribution by Pz,- Rewriting 209
= inf sup E 0e Ueu S-Ia (m~(UoQ))"
E
[R (8(STT) (Up, 2) J.UOQIN U.)]
(210)
From the construction of "hard instances", we know that for all U E U, t kk, Substituting this back in 210,
k).. Up = eat.
inf sup E #C02 Uell P~Pa, STa-()
E R (0(ST) (ear) {) U [o):]]
(211)
Note that the set fea: H is fixed and known. Consider, O₂ = (0) 0: ((x) x 3 + F), as
the set of algorithms. For every 8% O2, there exists 6% E O₃ which runs 8% using the input data, randomization 5, and the known set {ear Therefore, we can bound 211
2 e inf sup E BEBs Ueu S~Pe, sm ("a())))"
E [R (0(ST) 5), U Q1)).
(212)
30

---

Published as a conference paper at ICLR 2024
We have already proven lower bound for the above problem in Lemma D.3 specifically refer to equation 186 Substituting that result,
R (On. P)] 2 c10-2
[
ml/o2+ln(2)
(213)
guapa
0.99d
cc102
2k
3n
+In(2)
(214)
3m +ln(2)
(1 2exp( Tok )) 10-2
(215)
0.99d
Using n 2 40k, we can bound c 2 (1 expp In(4))) = 1 And, choosing n o we can
2-
3n +lu(2)
kd +2((2)
bound 1
2kg
2. Therefore, we have the result,
0.99kd
0.99kd
E Srppp
[ (On, P)] 2 100-2
(216)
31

---

Published as a conference paper at ICLR 2024
D.2 CNN UPPER BOUND
Theorem 7.2 (Formal). Let F. denote the class of functions represented by the set of locally connected neural network models, Mc(WW, defined in 66 Let the input data be drawn from the DSD distribution, S (DSD)", with a Ó ( We define the group 2 (Block (UI...., U+)
U, E (d), U, -. Then there exists weight initialization distribution W and update functions {F+r such that 0n (Mc[W) {Firr, W,, ) is an U-equivariant algorithm and, if k d are large enough, then
(s() max(O (o2(d A) (ndk)) 10).
(217)
for some constant 8 = 01))
Proof. The outline of the proof will run parallel the approach taken in the proof of Theorem 6.2 We will first present the algorithm 0n, then show it is Z/-equivariant algorithm and then derive the required sample complexity bound upper bound.
1. Algorithm Definition
To define the algorithm On. we need to specify its components: the model MMc W), the initialization distribution W, and the update functions {Fi)r. At iteration = O, we initialize the model parameter 100k-a?? and bias is set 6 0. The superscript
8 (wo, 6o] wD ~ (N(,,, where denotes the iteration number. To specify the update functions, we define the empirical loss function,
1: (W,
1/
(218)
j=1
The algorithm has T = 2 iterations. For simpler analysis, we divide the dataset, S"h into two equal sized datasets STn. and Sy with m 2 samples each. The update function for each E {1. 2} is.
ni Vedl(un. Fi = Ti n (w by
(219)
where 7/1 1/2 100 60 100 V (k++)) lu(ke) b2 10-4.
kd
2. Algorithm is Equivariant
To establish that 0, is U--quiivaraan,, we verify the three conditions specified in Definition 6 We define the group, V = [Block(V,I) I,) V E (()), where I is the identity matrix of size 1.
For æ, y E (X, )). U U4 w E Rd, E R4, choose V Block { (U", ,1) E V. without loss of generality, as for all i. U = U()) Then, the property of equivariance holds as,
Mc(ul(x) = Σ (sw (1)
Σ 2l (u()) -Moe))))MMMaaal
Mc. (Ux)....
(220)
1=1
For all /. E [2] and S.n E (K, )) the second property follows as,
U V u "Ve (Ve:
Ft S.
b
(221)
100) de ucn (Ve:
(w (w- Vel(u:: T0 w V..
(222)
U Cooo---Wlll Vel(s:
w ;b]
(223)
VF, STm
(224)
And as for property
3 observe that.
Ve U 20 060 d (wo 8
(225)
32

---

Published as a conference paper at ICLR 2024
holds for all V V.
3. Algorithm Analysis
We analyze the algorithm, with n max(2o²2 + d) In(kd), 10) samples, to establish that 6x achieve an expected risk of at most 5 2.5 10-3
3. We set 1 The outline of the
proof is follows: we first prove that after the first update step, the alignment of w² with unknown In the second step, use this alignment is reliably threshold out the
((V))) ft) "noise" patches, while letting the "signal" patch pass through the first hidden layer. We then show that this denoising effect, enables us to recover the signal with an alignment of 92(1), which would imply that the risk of the CNN on the task S ò.
signal vector w" is 2
3a. Update Step 1
We define ah = w V W O; (T"))) be the unnormalized parameter vector w and therefore the alignment with the signal is given by (w=))Tw² " (aa²)² =n To analyze uh we first evaluate the gradient with respect to wa, V Wollww) 0; STT).
V Wwll(w 0; 5Tt)
Yi
9 (o((w9)
(226)
17
k
Uj
Σ
Σ
2 % ((00))
(227)
i=1
1=1
k
h
22
1 -
Σ
Mī (w ( 20 )())
Σ
(228)
j=l
1=1
(229)
de (z().. We have used the facts that do is the identity function, and do is the where ((x) = d
constant function 1. And, ay == 1- 1 (w0)²² ( az) 33 Σ yyar!")
To further analyze 229 we first prove high probability bounds for ag. j E [m]]. From the initialization distribution W, we know that w 7E, where is the Gaussian random vector defined as e L2). And from the input distribution DSD, we know that aj = " + ae," for all in [k).. Here, ( ~ La) is also a Gaussian random vector, and ry = 1, if the signal patch appears in the j-th data sample appears in the i-th patch, and 0 otherwise.
k
0j = 1
(230)
1
rig Tw=
Σ Yn (1)
(231)
T ww Σ UnyoET (1) = 1 gET
E
(232)
We can now bound the range of ay as,
1 + I w0 |+| Σ YoE (1)
c 2 aj 21 1111 "ww 10'1-1 1 YocT (1)
(233)
We first upper bound hef "n='' Since the norm of the signal is 1, ||001|| TT w0 NO, 1), and
IyeTw" "0'
Took Ee "w'
< 8
(234)
33

---

Published as a conference paper at ICLR 2024
with probability - (010--1k22)) 2 1 10-6, for large enough k d. Next, provide an upper bound for x you" {
(6)
for all j. For this we analyze.
max ce(m]
Σ
rac = =ya
T (0)
max je(m]
4 ya max 5elml
VKEe
EglT
(235)
= = max je m
||l|| |c]| 6
T E, S GroVkd max JE m
c"c |cl
(236)
with probability 2 - 2 10-6 The last inequality 236 follows from the concentration of the norm of a Gaussian random variable, || 2 6vd]= < 2 exp(
36d
2d S 10-6. We define u = ]e]
- and
9j = u e,, which is standard Gaussian random variable. Then, from the concentration inequality,
Plmaxxe[m) |&l 2 (32lm(m)) S m x 10-6. Substituting this in 236
2
T max I jE[m]
9
S 6 / kd max lob
(237)
jE(m
S 6 ao ve 100 /k Inikdjs
V kd max legbs
(238)
,E _m(m]
6 100k=
kdd 32 Im(m) S b/
(239)
/ kutkdja
for large enough k, d. Using 234
239
in
233
we bound oj, for all j E [m], as,
1 + 1 w0
(6)
aj
1
(1)
(240)
AlGe
IV
IV
(241)
( d Also, note that B, = - 8
w* + tovke, We are now in the position to analyze wt!,
ri = w - -wl(w" : STH)
(242)
= w + 1
2zy
(243)
w + oo ookke)
w
+
20g
(244)
d w
20 -m
+
E,
(245)
122
m
where ě is the Gaussian random vector ~ Lo) Note that from the concentration of the norm of a Gaussian random variable [P[||||| 2 6 < 2exp(
36d
< 10-6. and P|||||| S vd/6] < 10-6,
2d
Recall that our aim is to bound "'''""""
(w (w"')""" w
For this, we first upper bound ||
1 I
11000
2 ² 0 +
w
20 /
m
(246)
m
|
Em 9
w
+
m
(247)
m
772
2011
+
Gd
(248)
>>||=||
+
+
b क Intkaj
(249)
2
ov7
5 +
6kd
10
kd
(250)
o In(kdj
(k+d) (nd)))
34

---

Published as a conference paper at ICLR 2024
for large enough k, d. Similarly, we lower bound ||
||.
20
m
||
2 Ey
og
200 11,
(251)
m
m
2811
30
|
||,
(252)
3d
kd lu(kd)
GV 10
kd In(ka)
(253)
66
V
where the last inequality holds for a large enough k, d. Next, we lower bound (w )"
(w " " = (/0))"u " + "ii= oj
(ww) "²" 2 - a (e)" w",
(254)
2 - aj
20 E oz (E)"'0²
= 7 w +
(255)
2 -11e" T "
+ 3
(E) "'
(256)
Vm
283
8
+
3 2
(k++) lu(kd)
Bo
(()T
(257)
2
8
11
T2
w
TO
2 To.
6
(258)
with probability 2 1 - 1
81
1 - 10 6, And similarly we upper bound (w")
10
(w ~t <
1 w0
50y
(Et)"
(259)
vm
54
1 4.
(260)
kd Therefore, V In(d]
2 (w "
2
6
V In(d)) with probability 2 1 - 10-5 We
kd
100
can now express w Aw= + 11 such that 40 (k+t)) || || = 1, and (w+) ) = 3b. Update Step 2
kd
X
kd
100
(k+d) (kd)
In this step, we will now show that the 100 V (k+dj (kd) alignment achieved in the first step, enables the network to filter out the noise patches, while letting from the signal patch pass through. This denoising will enables us to achieve a stronger a 1 10-3 alignment with the signal vector.
Rd
We begin by analyzing the push forward of all noise patches in ST through the CNN model,
max [e]])
(aw ) (0) ك
)Te,))
max /k
(261)
(.
100 /1n(kkn 3/2 In(o2k(( + d) In(kd)),
(262)
1 S
kd
(263)
4vK
100 (l(k))
To derive inequality 262 we have used the concentration of the maximum of the absolute value of mk
ii.d. Gaussian random variables, [Pfmax,, , (ww )Te, JT,50 2 lnmk)) S (mkps I 10-6.
(4)
Recall
from the analysis of the first update step that,
kd / (k+4d) In(ka) (w (Tu))Tw= "
kd V (k+-d) In(ad)
(264)
From 263
264 and bj
kd we filter out the noise and let the signal pass for all j.
100 (+td)l((ka)
40 (k+dd) (n(kd]
kd
Sb, (2) (w 1T (0)) 2 100 V (k+d) In(kaj where rig =
kd
(265)
(1) dh, (y1 (w)) Tar = O, where rij =0
(266)
We will follow in the footsteps of update step 1 and seek to bound (w2) wn First, we define 2 = w' 7/2 w b1; STt), and therefore (w2)Tw" w = ( the gradient of the empirical loss function with respect to w
15 Now, we begin by evaluate
35

---

Published as a conference paper at ICLR 2024
4/
Vwil(w' (=:
-1
2
Vj
Σ
Sb (ww ) 22)"1)))
Σ
2j bb, (120 ((=0))=z)) [,,
(3)
m
==1
(267)
k
k
2
1
Σ
Sb (
Σ
(268)
==1
t=1
where 268 follows from 265
266
Define oj == 1 - Σi= Ub (1y (w= 2 1), for j E [a] \ [m]
Then, 2 1 100 V (k++) (kay 2 0j
kd
kd 400 (k+d) kn(kd We also define ar (2) be the patch
of the j-th data sample that corresponds to the occurrence of the signal, that is raj = 1. From 268
Vwil(w', bb;
20zyfar
(1)
20g
(w" + aae.")
(269)
m
m
m
20
w
20a çj
(1)
(270)
m
m
f=1
j=1
m
d
20 w
20 m a
E,
(271)
m
172
where é (O Ia). We define a norm of a Gaussian random variable P[[|@| 2 m now ready to bound (w²)T "=
201
And, observe that from the concentration of the
6vd S 2exp(
36d
S 10-6, With these results, we
2d
( 'n=
| 1/w 1/2
20, w 1/2
to 20
m
m
1=1
< + ama
[wwl 1rmp||w"]
+
20
||]||
< + ar/2
+
12
S 1 + 12 10-3),
(o In(kd)
for large enough k, d. And now we lower bound (w²)) w
(w:)T = = " + 1/2
m
20
(w*)7
"o""TT''
"= + 1/2
mm (a,)
ēT ==
(272)
m
m
j=1
d -(w "nn + 122
E 203
+ 1/2
20
(EN(O. 1),
(273)
2 -1 + 1/2a
2n20r
(274)
Vm
2 -1 + 72a - 1/2
20e
2 211 (2 10-
(275)
(k+ In(dd)
where we have used the fact that TP[|
2c
10 10-3) holds with probability & 10-6 6 for
v (k+ In(ka]
large enough k; d. Therefore the alignment can be lower bounded as,
(10
1+10" 1+10" 2 0.96.
(276)
as 2 a 2 3
for large k, d, and this occurs with a probability 2 1 x 10-5
3c. CNN has Low Risk
We now show that this large constant alignment guarantees low risk. We bound the push forward of the noise through the CNN,
la max ((w TTe)) %E(m]
/00 In(ka]] S 10-1
6 i
(277)
36

---

Published as a conference paper at ICLR 2024
To derive the last inequality, we have used the concentration of the maximum of the absolute value of & ii.d. Gaussian random variables, [[maaxe(()) ( e,l 2 [n(k]] data sample, let é [k] be the index of the signal patch, then,
2
I 10 6. For this
("x ) 2 0.959, Tba (w) )"
(278)
Tb (1)( )" ) = 0, Vi
(279)
To bound the risk in the failure case, we note that for any W,
k
[1
s (wr" x: (1())))] = [1( bolw x (0))))
(280)
E [11 -
Σ dos cyw ax 10)))
(281)
(a. SSD)
E
Σ (o(())))) Φs (b(cos(aj) + }
(282)
j=1
To evaluate the above expression, observe that the expectation can be written as,
E1(1- - Σ
(b(())))) (c(cos(aj) + (()))) = Var((1
Σ on(oss)) db(cos((a)) +
ifj
ifj
+ +[[(1 - Σ db (orEs)))) (s(c(s(a)) + re;))))? (283)
Σ Varlos(ac;;) + Var (ccs((())( + or + (B(o)(cos((ss) + o(r))))
(284)
Σ o² + cos cos) S ko² +1
(285)
Substituting this back,
BI(y Σ po(wy x 1))
S 1 Σ>
2 2
(286)
5=1
Finally, the risk of the classifier is,
E R (0n, P)] S (1 -0.959) + 4 10 < 8.
(287)
37

---

Published as a conference paper at ICLR 2024
E EXPERIMENTS
In this section, we validate theoretical bounds with empirical results. We begin by presenting the test-error experiments, where we evaluate the test error of the three models across various training sample sizes. The results for these experiments show an under-of-magnitue decrease in the sample efficiency when comparing CNNs to LCNs, and comparing LCNs to FCNs.
We then present our sample complexity experiments, wherein we explicitly calculate the sample complexity of CNNs and LCNs for various (k, d) pairs. However, these experiments are significantly more compute-intensive than the test error experiments. While the computational demands are manageable for CNNs, they increase significantly for LCNs and become prohibitively large for FCNs. This is primarily because FCNs require at least 10-20 times more samples than LCNs. Nonetheless, for both CNNs and LCNs, we successfully verify that the empirical sample complexity satisfies the respective theoretical bounds. Specifically, for CNNs, we show O(k) sample complexity growth with fixed d and a (d)) growth with fixed k. For LCNs, we establish that the sample complexity grows as O(k)), (2kk with a fixed and as (d) with a fixed k.
E. TEST ERROR EXPERIMENTS
In this experiment, we evaluate the test error of each of the three models when trained with sample size of (10, 50, 100, 250, 500} for every (k:, d) pair with k d E {10, 20]. For each training session, we conduct grid search over the learning rates for patch parameters being {10-1, 10 10-3), }. and for the biases being {10-2, 10-8, 10-2). 3. We choose the model with the lowest test error. The
experiment is replicated 5 times, and we report the mean and standard deviation of the test errors.
Toa Free for 1-11, 1-10,, amo
Ted Freee for 1-10, 4-20, and
0.7
07-
IC1
LCE
04
PC5
PCS
05-
044
1044
0.-
0.1
0.8
0.0
96
Natber/ of Triikig Sempes
Manterr Thirigg Semples
THe Frree for 20: 6-10, an01
12 THi Erec for 20:20 4:70, end
03.
IC1
ICE
PC5
P0
07-
0.
044
03
02-
41.
Namber of Srarnng Serciis
Narberr Tiiring Semppes
Figure 1: Test error incurred by CNNs, LCNs and FCNs for various values of (k:, d)
Across all (k, d) pairs we observe that LCNs require an order-of-magniuude (10-20 times) more samples than CNNs to achieve comparable test errors. This demonstrates the larger sample efficiency of CNNS over LCNs. Extrapolating the trend line for FCNs, it is evident that they would need even orders-of-maanituue magnitude more samples than LCNs for comparable error levels. These observations consistent with our theoretical predictions of sample complexities: ((12d) for FCNs, ( + d)) and Q(k-d) for LCNs, and O(k: + d) for CNNs.
38

---

Published as a conference paper at ICLR 2024
E.2 SAMPLE COMPLEXITY EXPERIMENTS
In our first experiment, we fix the patch dimension d at 20 and vary the number of patches & across the range (10, 15, 20, 25, 30). For each (k; d) pair; we plot the sample complexity for both CNNs and LCNs. We evaluate the sample complexity via the following steps:
Target Loss Evaluation: We compute the optimal loss based on the ground truth and add fixed tolerance of 0.03 to establish the target loss.
2. Determining Sample Range: Through trial and error, we determine that maximum of 1000 samples is sufficient for any model across all values.
3. Binary Search Method: To find the minimum number of samples required to reach the target loss, we perform binary search. In each step, we conduct grid search over the learning rates for weights being [10 10 10 3] and biases being [10 2, 10 10 4), and select the model with the lowest test error.
4. Repetitions for Reliability: We repeat the steps (1-3) five times, plotting the mean and standard deviation of the sample complexities.
CUN Sample Compleelyy with (-28,
LOV
Samie Compoee
15-
12
25
Figure 2: Sample complexity for CNNs (left) and LCNs (right) across various values of k
For fixed d, the sample complexity for CNNs exhibits ((k) growth (Figure 3, left), which consistent with our CNN upper bound. Similarly, for LCNs, the complexity growth consistent with our theoretical results of O(k2) and s2(k) (Figure 3, right). Additionally, note that LCNs require about 10 to 20 times more samples than CNNs, which corresponds to the multiplicative d factor in LCNs' sample complexity bound.
In our second experiment, we set the number of patches i at 20 and vary the patch dimension d across the range [10, 15, 20, 25, 30). The same steps (I-4) are repeated for this setup.
CUN Sample Complaxkly with 1020 p-0.1
LON Sample Campllatty with b-20 c=L.)
Seedh CorpAce
Sample Consleeko
Telt pat.parrrrrrr
Figure 3: Sample complexity for CNNs (left) and LCNs (right) across various values of
39

---

Published as a conference paper at ICLR 2024
For fixed k, observe that the CNN sample complexity grows O(d) (Figure 4, left), and the LCN sample complexity grows as (d) (Figure 4, right), both in line with our theoretical guarantees. Furthermore, akin to findings in the first experiment, LCNs require approximately 20 times more samples than CNNs, owing to the multiplicative & factor in their sample complexity.
40


Reviews:
[{"review_id": "8MyKBcXtWe", "reviewer": "Reviewer_LSto", "summary": "This work provides a theoretical analysis of the sample complexity of Convolutional Networks (CNNs), Local Connected Networks (LCNs), and Fully-Connected Networks (FCNs). This paper claims that CNNs are more sample efficient than LCNs, which in turn are more sample efficient than FCNs when the data has implicit locality and translation invariance properties, as is the case with visual data. The authors prove lower bounds on the sample complexity of FCNs and LCNs, and similarly demonstrate upper bounds on the sample complexities of LCNs and CNNs to draw firm conclusions under the assumptions made in their theory.\n\nTo carry out the analysis, the paper proposed a toy data model inspired from the concepts of locality and translation invariance in natural images, called the Dynamic Signal Distribution (DSD) task. Here the input is comprised of k consecutive patches of dimension d, and one of the k patches is randomly filled with a noisy signed signal, while remaining patches are filled with isotropic Gaussian noise. A binary label for the input is determined from the sign of the signal.", "questions": "Please provide numerical experiments with synthetic data under the DSD model and one-layer CNNs, LCNs, and FCNs, and examine the empirical sample complexity of this model as you vary the quantities of interest ($\\sigma$, $k$, $d$).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "### Significance\n* While the results agree with empirical intuition that inductive biases in the model reflecting properties of the data should improve sample complexity, it is interesting to see such a result made crisp for vision models, and with specific focus on the locality and translation invariance properties of visual data.\n\n### Clarity\n* The analysis is non-trivial and requires heavy notation; the paper does a good job at walking the reader through the intuition, proofs, claims, and findings, however much of the theoretical development is relegated to the appendix.\n\n### Originality\n* The authors theoretical analysis is quite unique in my opinion. To the best of my knowledge, the proposed DSD model is novel, and the derived lower bounds are enabled by taking the learning algorithm (gradient descent) into account. This is necessary since a learning algorithm can simulate CNNs with LCNs and FCNs. While previous works have established a sample complexity separation when assuming training with gradient descent, they used a data model which did not seek to capture translation invariance and locality.", "weaknesses": "The main weakness in my opinion is step connecting the theoretical findings to practice. Given the theoretical contribution, I do not expect an in-depth empirical analysis with deep networks; however, I would to see numerical results demonstrating the derived theory under the DSD model. It is fine to constrain to single hidden layer networks as is done in the theory.\n\n** Minor point, but in notation it is stated that vectors are indexed at 1, but on page 4, $\\mu_i[(i-1)d:id]$ is indexed at 0.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8RIt8f8W3U", "reviewer": "Reviewer_yeJ4", "summary": "The authors proof that CNNs has a better sample complexity than LCNs, and LCNs has a better sample complexity than FCNs under the framework of Dynamic Signal Distribution.", "questions": "Can the current framework support ReLU like activation functions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Theoretical proof is provided regarding the sample complexity of FCNs, LCNs, and CNNs. The theoretical proof is built upon several tools like Dynamic Signal Distribution (DSD), network architectures given DSD, equivariant algorithms, minimax risk, etc. Overall speaking, the paper is well-organized and easy to follow even for general audience.", "weaknesses": "1. The Local Signal Adaptivity (LSA) activation function is quite different compared to popular used activation function, like ReLU or more recent activation function. A better justification of using LSA could be provided. \n2. From the proof sketch in section 6 and section 7, it seems that the sample complexity is dependent on what is the learning setting. For example, in section 6, 'we establish that learning U ◦ DSD with m samples requires learning k \"nearly independent\" subtasks,' and in section 7, 'we establish that learning U ◦ DSD with m samples requires learning k independent subtasks.' Dose this result in the difference between the sample complexity of LCNs in section 6 and 7? If this is the case, I think authors could add more analysis regarding how the results will change given the learning setting of 'U ◦ DSD', In addition, is there a setting where the sample complexity of FCNs, LCNs and CNNs is similar? I hope authors could provide more insights regarding this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OtjifWU7VA", "reviewer": "Reviewer_jtyo", "summary": "The authors study the problem of sample complexity for different classes of models based on analyzing an equivariant gradient descent type algorithm.", "questions": "- I am curious if transformers can be described by FCN or LCN, or if they need a totally different treatment. I think this would be an interesting discussion point to add if there is any insight because the sample complexity for transformers is a relevant and interesting topic.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The relation between sample complexity and the type of network is interesting.\n- There seems to be real improvements over previous works.", "weaknesses": "The only downside I see to this work is the fact that there is no empirical result which supports the theoretic result. I myself cannot find any issue or criticism with the theory that was presented, but the complexity and abtractness of the setting and the numerous variables involved makes it difficult to find any error in the derivation if one exists.\n\nTherefore, it seems that there needs to be some empirical result of the predicted complexity and an actual observation rather than just a standalone theory with no phyisical evidence to support it. It seems that the problem setup is precise enough to run small experiments on the linear models outlined in section 4.2. \n\nFor example, for a fixed amount of $sigma$ and $d$, each linear model can be trained on an increasing number of classes to show the empirical observation of the $k$ term. Similarly, this can also be shown with a fixed $sigma$ and $k$. This is just the first example of what came to mind, but the authors may indeed be able to come up with an even better experiment given their study of the problem.\n \nIf this can be added, I would be happy to raise my score. \n\n## Minor:\n\nAfter the conclusion, there is a QED symbol which is likely a typo and should have appeared after the previous section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LU7mrnXNe7", "reviewer": "Reviewer_o7GU", "summary": "In this research, they investigate the superior performance of Convolutional Neural Networks (CNNs) in vision-centric tasks in comparison to Locally Connected Networks (LCNs) and Fully Connected Networks (FCNs). They introduce the concept of Dynamic Signal Distribution (DSD), an intricate data model devised to encapsulate inherent properties observed in real-world imagery, notably locality and translation invariance. Within the framework of this study, they establish a theoretical sample complexity separation between CNNs, LCNs, and FCNs, taking into account optimization considerations.", "questions": "No.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is well-written and provides very supportive technical details. The authors introduce an interesting data model called DSD to represent real-world vision tasks. This task is straightforward and simple, making it suitable for theoretical analysis. Additionally, this task exhibits characteristics of locality and translation invariance.", "weaknesses": "Primary Concerns:\n\nNovelty. My main reservation pertains to the novelty made over the work by Wang & Wu (2023). While I concede that the task depicted here is more realistic than that in Wang & Wu (2023), it appears the core insights remain consistent: FCNs are equivalent to global rotation groups, whereas LCNs relate to local rotation/permutation groups. Although the authors consider optimization in the upper bound analysis for LCNs and CNNs, the chosen algorithm, which has just two training iterations, seems quite unconventional and perhaps too simplistic. I'm uncertain whether this presents an improvement relative to the ERM analysis. Regarding the lower bound section, if I interpret it correctly, does the novelty lie mostly in the technical novelty? It appears that the primary objective is to determine the size of the enlarged function class, when the original task is enlarged by the global/local rotation group. I question the significance of the specific method used for this calculation. My primary concern remains to be the novelty over Wang & Wu (2023). If clarity on this point is provided, I'm inclined to upgrade my rating to at least 6. Moreover, it would be beneficial if the paper could elaborate more on the contributions of Wang & Wu (2023) and comparisons with Wang & Wu (2023). For instance, when stating on page 2, \"Wang & Wu (2023) extended this line of work to show a separation between FCNs, LCNs and CNNs. However, that work suffer from the same drawbacks as Li et al. (2021).\", a more explicit discussion on the advancements and remaining problems in Wang & Wu (2023) would be useful.\n\nSecondary Concerns:\n\n1. Regarding the model definitions, what is the reason for limiting the norm of $w_i$ to less than one? This seems implausible.\n2. What necessitates the width of your FCN models to be defined as $k$? Shouldn't the lower bound be applicable to any width, at least intuitively?\n3. Concerning the proof outline for theorem 6.1, in its first step, could there be an inclusion of a more comprehensive technical elaboration? While some readers might be able to grasp its logic intuitively, offering a detailed technical justification, especially given its novel approach, would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)