On the Inductive Bias of a CNN for Distributions with Orthogonal Patterns
Authors: Alon Brutzkus
Amir Globerson
Venue:  (2021)
Keywords: Deep learning theory
generalization
overparemeterization
CNN

Abstract: Training overparameterized convolutional neural networks with gradient based optimization is the most successful learning method for image classification. However, their generalization properties are far from understood. In this work, we consider a simplified image classification task where images contain orthogonal patches and are learned with a 3-layer overparameterized convolutional network and stochastic gradient descent (SGD). We empirically identify a novel phenomenon of SGD in our setting, where the dot-product between the learned pattern detectors and their detected patterns are governed by the pattern statistics in the training set. We call this phenomenon Pattern Statistics Inductive Bias (PSI) and empirically verify it in a large number of instances. We prove that in our setting, if a learning algorithm satisfies PSI then its sample complexity is $O(d^2\log(d))$ where $d$ is the filter dimension. In contrast, we show a VC dimension lower bound which is exponential in $d$. We perform experiments with overparameterized CNNs on a variant of MNIST with non-orthogonal patches, and show that the empirical observations are in line with our analysis.

Under review as a conference paper at ICLR 2021
ON THE INDUCTIVE BIAS OF A CNN FOR DISTRIBU- TIONS WITH ORTHOGONAL PATTERNS
Anonymous authors Paper under double-blind review
ABSTRACT
Training overparameterized convolutional neural networks with gradient based optimization is the most successful learning method for image classification. However, their generalization properties are far from understood. In this work, we consider simplified image classification task where images contain orthog- onal patches and are learned with a 3-layer overparameterized convolutional net- work and stochastic gradient descent (SGD). We empirically identify a novel phe- nomenon of SGD in setting, where the dot-product between the learned pattern detectors and their detected patterns are governed by the pattern statistics the training set. We call this phenomenon Pattern Statistics Inductive Bias (PSI) and empirically verify it in a large number of instances. We prove that in our setting, if learning algorithm satisfies PSI then its sample complexity is (dd log(d) where is the filter dimension. In contrast, we show a VC dimension lower bound which exponential in d. We perform experiments with overparameterized CNNs on a variant of MNIST with non-orthogonal patches, and show that the empirical observations are in line with our analysis.
INTRODUCTION
Convolutional neural networks (CNNs) have achieved remarkable performance in various computer vision tasks (Krizhevsky et al.) 2012, Xu al. 2015: Taigman et al., 2014). In practice, these net- works typically have more parameters than needed to achieve zero train error (i.e., are overparame- terized). Despite non-convexity and the potential problem of overfitting, training these models with gradient based methods leads to solutions with low test error. It is still largely unknown why such simple optimization algorithms have outstanding test performance for learning overparameterized convolutional networks.
Recently, there have been major efforts to provide generalization guarantees for overparameterized CNNs. However, current generalization guarantees either depend on the number of channels of the network (Long & Sedghi 2020) or hold under specific constraints on the weights (Li et al. 2018).
Clearly, the generalization of overparameterized CNNs depends on both the learning algorithm (gradient-based methods) and unique properties of the data. Providing generalization guarantees while incorporating these factors is a major challenge. Indeed, this requires analyzing non-convex optimization methods and mathematically defining properties of the data, which is extremely diffi- cult for real-world problems. Therefore, it necessary to first understand simple settings which are amenable to theoretical and empirical analysis and share salient features with real-world problems.
Towards this goal, we analyze simplified pattern recognition task where all patterns in the im- ages are orthogonal and the classification is binary. The architecture is a 3-layer overparameterized convolutional neural network and it is learned using stochastic gradient descent (SGD). We take a unique approach that combines novel empirical observations with theoretical guarantees provide a novel generalization bound which is independent of the number of channels and a low-degree polynomial of the filter dimension, which is usually low in practice.
Empirically, we identify a novel property of the solutions found by SGD. We observe that the statis- ties of patterns in the training data govern the magnitude of the dot dot-product between learned pattern detectors and their detected patterns. Specifically, patterns that appear almost exclusively in one of the classes will have large dot-product with the channels that detect them. On the other hand,

---

Under review as a conference paper at ICLR 2021
patterns that appear roughly equally in both classes, will have low dot-product with their detecting channels. We formally define this as the "Pattern Statistics Inductive Bias" condition (PSI) and pro- vide empirical evidence that PSI holds across large number of instances. We also prove that SGD indeed satisfies PSI in a simple setup of two points in the training set.
Under the assumption that PSI holds, we analyze the sample complexity and prove that it is at most O(d log d), where d is the filter dimension. In contrast, we show that the VC dimension of the class of functions SGD) that will have exponential sample complexity. Together, these results provide firm evidence that even though SGD can in principle overfit, it is nonetheless biased towards solutions which are determined by the statistics of the patterns in the training set and consequently it has good generalization performance.
consider is exponential in d, and thus there exist other learning algorithms (not
We perform experiments with overparamterized CNNs on variant of MNIST that has non- orthogonal patterns. We use our analysis better understand why SGD has low sample complexity in this setting, We empirically show that the inductive bias of SGD is similar to PSI. This sug- gests that the idea of PSI is not unique to the orthogonal case and can be useful for understanding overparameterrzee CNNs in other challenging settings.
2 RELATED WORK
Several recent works have studied the generalization properties of overparameterized CNNs. Some of these propose generalization bounds that depend on the number of channels (Long & Sedghi 2020 [iang et al., 2019). Others provide guarantees for CNNs with constraints on the weights (Zhou & Feng 2018 Li et al. 2018). Convergence of gradient descent to KKT points of the max-margin problem is shown in Lyu & Li (2020) and Nacson al. (2019) for homogeneous models. However, their results do not provide generalization guarantees in our setting. Gunasekar et al. (2018) study the inductive bias of linear CNNs.
Yu et al. (2019) study a pattern classification problem similar to ours. However, their analysis holds for an unbounded hinge loss which is not used in practice. Furthermore, their sample complexity de- pends on the network size, and thus does not explain why large networks do not overfit. Other works have studied learning under certain ground truth distributions. For example, Brutzkus & Globerson (2019) study simple extension of the XOR problem, showing that overparameterized CNNs gener- alize better than smaller CNNs. Single-channel CNNs are analyzed in (Du et al.) 201 8h & Globerson 2017 Du et al. 2018c).
Brutzkus
Other works study the inductive bias of gradient descent on fully connected linear or non-linear
networks (Ji & Telgarsky| 2019 Arora et 20199 Wei et al. 2019 Brutzkus et al. 2018 Dziugaite
Fully connected networks were also analyzed via the NTK approximation (Du et al. 2019 2018d Arora et al.) 2019b] Fiat et al. 2019))
& Roy| |017] Allen-llen-Zn et al. 2019 Chizat & Bach 2020).
Kushilevitz & Roth (1996); Shvaytser] (1990) study the learnability of visual patterns distribution.
However, our focus is on learnability using specific algorithm and architecture: SGD trained on
overparameterized CNNs.
THE ORTHOGONAL PATTERNS PROBLEM
Data Generating Distribution: We consider a learning problem that captures key property of visual classification. Many visual classes are characterized by the existence of certain patterns. For example an 8 will typically contain an x like pattern somewhere in the image. Here we consider an abstraction of this behavior where images consist of a set of patterns. Furthermore, each class is characterized by a pattern that appears exclusively in it. We define this formally below.
Let P be a set of orthogonal vectors in Rd, where |P| S d. For simplicity, we assume that |pl|a 1 for all p E P. We consider input vectors æ with n patterns of dimension d. Formally, æ (x[1),.... [n]] nR where æ[i]] P is the ith pattern of æ and n < d. We denote é x if x contains the pattern E P Let P(x) = {p E æ p P) denote the set of all patterns in æ.
We say that æ contains p if there exists such that ær5] =
2

---

Under review as a conference paper at ICLR 2021
Next, we define how labeled points are generated. Consider three non-overla sets of patterns: P-,P.. . Ps = P whose disjoint union is P. P. is the set of positive patterns, P- the set of negative patterns and P, is the set of spurious patterns. For simplicity, in this work we consider the case where [P.| |P-|= 1. We denote, P {P1. P PP......PP Pip ). P_ {p1} and P- {p2]. For convenience, also refer to a set of patterns A as a set of the indices of the patterns, .c.g., we denote i E A if p; E A.
We consider distributions D over (2r,) E IR'' {=1} with the following properties: (1) 1) P (y= -1) and randomly choose set of n patterns from P.. Denote this set of n chosen patterns by A. Let be some æ' such that P(x')= A, i.e., the location of each pattern in is chosen arbitrarily For example, if n = 3 and the n-1 patterns are P3- Py this can result in samples such as ([P). P7. P3 or ([P3. PP],, 1). (3) Similarly for y 1, only choose P2 & P_ instead of Pt-
(2) Given y = 1, a vector æ is sampled as follows. Choose the positive pattern P1
We will consider several distributions that satisfy the above and have different sampling schemes for the spurious patterns (see Sec. 77) Fig. 4 in the supplementary shows an example of samples generated using the above procedure. Note that any distribution which satisfies the above is linearly separable and each vector x can be classified solely based on whether P1 6 x or P2 E x.
Neural Architecture: For learning the above pattern detection problems, a natural model in this context is a 3-layer network with a convolutional layer, followed by ReLU, max pooling and a fully- connected layer. Each channel in the first layer can be thought of as detector for given pattern. We say that a detector detects pattern p E P. if p has the largest dot product with the detector among all patterns in P, U., or P_ L., and this dot product is positive For simplicity we fix the weights on the last linear layer to values +1
Let 2k denote the number of channels. We partition the channels into two sets: (1) ,...... (k) and u1)), ,..,,,.., (k). These will have weights of +1 and -1 in the output respectively. Finally, let W 22 be the weight matrix whose rows are ( followed by (
For an input x (a[1),.... x[n])= E Radd where x[i] é R2 the output of the network is:
Nw(x)= = Σ max fo (w xbi))> max fo (u(") (u))>(()))
xb]i}}]
(1)
where (I) = ma, is the ReLU activation. Let H. denote the class of all networks Nw in Eq. [ with k O. Finally, we note that H can perfectly fit the distribution D above, by setting k == 1. w P1 and (1) P2- Therefore, for k > 1 the network is overparameterized.
Training Algorithm: Let S be a training set with m IID samples from D. We consider minimizing
the hinge loss: <(W)- 1 (m...))s max y/ Nw (a:),, For optimization, we use SGD with constant learning rate 1). The parameters W are initialized as IID Gaussians with zero mean and standard deviation og. Let W, be the weight matrix at iteration t of SGD. Similarly let w u, be the corresponding vectors iteration f.
(i)
We now define the notion of detection ratios. The detection ratios are a property of the model and will be key to our analysis. We first define the set of neurons that are maximally activated by pattern p, among all patterns in P. u P. (i.e., all detectors of pattern p
Detection Ratios:
W W j arg max ()) Pp: = w P, 0
EPP.UP.
ut(1)
arg max u () .D: = = (1) lePLUP,
Dp >
Next we define (t) Ejew ()) P. and (1) = (j ue p. The quantity Mc (1) is the sum of the dot products between a pattern P; and its detectors w ()) M (1) can be interpreted
The order of the patterns will not matter, because the convolutional network is invariant to it.
'The reason we consider these sets of patterns will be clear when discuss detection ratios.
4 "Note that this does not affect the expressive power of the network.
Given tie hetween sets, we assume the weight is assigned arhitrarily to of them.
3

---

Under review as a conference paper at ICLR 2021
as the overall response of w() detectors of pattern P... Similarly, we define My (t), which is like Mt (i), only with detectors v())
For all P. P. U Ps we refer to (1( as positive detection ratios. The detection ratio can be interpreted as the ratio between the undesired response of pattern detectors of p, and the desired response of discriminative pattern detectors (detectors of PT). Therefore, we would like this ratio to be small. Indeed, for any positive point x" we have that:
(.)
Nw (x (1) Σ Ma(1) M (1- Σ
(5) D.EP.uP, My (1)
(3)
P,ePauP.
where the inequality follows since positive points have only patterns in P. U P... by Eq. D and the definitions of (i) and (i). Notice that if all positive detection ratios are small, then the positive point is classified correctly. We will empirically show that for SGD, the magnitude of the detection ratios are governed by the statistics of the patterns in the training set, which will imply our generalization result.
Similarly, we define W (1),2( (1) and (T()) where the only difference is using P- in- stead P.. Furthermore, for all p; E P_UP, we say that (.)()) are negative detection ratios. Then, M,
as in Eq. we have for all negative points x" that: -Nw (x) ) > (2 (1 Ep,eP,up. (2)
(.)()
This shows that if negative detection ratios are small, then all negative points are classified correctly. In the rest of the paper, we refer to both positive and negative detection ratios as detection ratios.
In given training set, patterns will appear in both positive and negative examples. The following measure captures how well-balanced are the patterns between the labels. For any pattern P; P, define the following statistic of the training
Empirical Pattern Bias:
8
リソ (p, E xz
(4)
m
The detection ratios define quantities of the learned model. On the other hand, Eq, is a quantity of the sampled training set. In the next section, we define the PSI property, which specifies how these two measures should be related to guarantee good generalization for the learned model.
PATTERN STATISTICS INDUCTIVE BIAS
The inductive bias of learning algorithm refers how the algorithm chooses among all models that fit the data equally well. For example, an SVM algorithm has an inductive bias towards low norm. Understanding the success of deep learning requires understanding the inductive bias of learning algorithms used to learn networks, and in particular SGD (Zhang et al. 2017).
In what follows, we define certain inductive bias of an algorithm our setting, which we refer to as the Patterns Statistics Inductive Bias (PSI) property. The PSI property states simple relation between the relative frequency of patterns 8; (see Eq. [4] and the detection ratios. We begin by providing the formal definition of PSI, and then provide further intuition. For the definition, we let be any learning algorithm which given a training set S returns a network A(S) as in Eq. [
Definition 4.1. We say that learning algorithm A satisfies the Pateerns Statistics Inductive Bias condition with constants b.c,& 5 > 0 ((b,c,8)-PSI) if the following holds. For any m 2 1, 1 with probability at least 1 8 over the randomization of A and training set S of size m, A(S) satisfies the following conditions:
(1())
Vie P. UP.:
5mmx
0
(5)
(1(
81
m
())
ViE P. UP.:
< mmx
(6)
(2)
82
mm
WWe state for simplicity. Alternatively, one can assume m for constant C.
4

---

Under review as a conference paper at ICLR 2021
We next provide some informal intuition as why SGD updates may lead to PSI (in Sec. provide a proof of this for a restricted setting).
We will consider updates made by gradient descent (full batch SGD). Define W (i) to be the set (i) with weight vectors (0) instead of w((), Similarly, define Ui (t), W
and Uj (i).
Throughout the discussion below, we assume that these sets have roughly the same size 0 We will
show that in certain cases, high value of - implies that the detection ratio (. has high
(L)
value. Furthermore, a low value of - implies a low value of (.) (T)" This motivates the bound in the PSI definition. As we will show, this follows since the statistics of the patterns in the training set St. govern the magnitude of the dot-product between a detector and its detected pattern.
By our distribution assumption should have 51 1.2 First assume that s; - for P, P... i.e.,
#1 1. Now lets what the detection ratio M[(1) should be by the gradient update. Note that M2,
8,
the gradient is a sum of updates, one for each point in the training set. Assume that j e W; (1), i.e. wo()) detects Pt- Then by the gradient update, the value PP is added to w² for all positive points that have non-zero hinge loss. The value - -; is also added for few P; P_ u P, and a subset of the negative points (i depends on the specific negative point). In the next iteration, holds that j E w (1) and the updates continue similarly. Overall, we see that w P1. which is the dot- dot-producc between the detector and its detected pattern, increases in each iteration and should be large after few iterations. Therefore, M (1) should be large. By exactly the same argument, we should expect that for j E U (1), u. PP increases in each iteration and now (i) should be large. Under the assumption that (25 (1) > IWT (1)), we should have M (1) as well. Therefore, (1)
if 21 # then should expect that (1) (1)
1.
On the other hand, if p, appears in roughly an equal number of positive and negative points, i.e., 8 x 0, then we should expect (i) to be low. To see this, consider a filter j U, (i). In this case, positive points that contain P; and with non-zero loss add P, to v,)), while negative points that contain P; and have non-zero loss add " P; Thus, u, p, should not increase signficantly. Therefore, both (C) (T) and =tt should be small in this case.
Given the intuition above, one possible conjecture is that the detection ratio MC M
is bounded by an
affine function of max (- s. 0). which leads to the PSI condition in Definition
The bias term in the affine function takes into account that our intuition above is not exact, Finally, y, we can make a similar argument for &i for motivating Eq.
#2
VC DIMENSION BOUND AND RELATION TO PSI
Here show that the architecture in Section 3 is highly expressive, and can thus potentially overfit and generalize poorly. Morcover, we show examples of networks that overfit and do not satisfy PSI. First, a simple argument shows that VC(H)) s (.) in our setting. The proof is given in Section A
The lower bound below is more challenging, and reveals interesting connections to the PSI property.
Theorem 5.1. Assume that 2n and 2 2, then VC(H) -
The full proof is given in Section B Here we give a sketch. We construct a set of size 2n 2 that can be shattered. For a given E {0, 10 let [[j]] be its jth entry. For any such 1, define point xy such that for any s j s n - 1, x1 = I[ippgn1 (1 I[5])P2512 Furthermore, arbitrarily choose æ [n] P1 [y[n] P2 and define B (xr [ (0.1)==1) Assume that each point æ, e B has label yı- We define a network with filters (1) max {a,, Eisjsn- my[i] and
This holds with high probability at initialization for sufficiently large network. Furthermore, in Section we show that it holds during training in the case of two training points.
7
We consider max (- -a
in the PSI definition because the detection ratios non-negative.
5

---

Under review as a conference paper at ICLR 2021
num occurences
D
102
D
0.10
10
0.05
109
0.00
0.0
0.5
1.0
0.0
0.5
1.0
50
5000
10000
max
&
(a)
(c)
Figure 1: Empirical analysis of c". (a) Empirical calculation of c* for Du and Doc- Values are in M. and (g
log scale. (b) c* as a function of the network size k (c) Positive correlation between
max (-210) The depicted line is the best PSI bound with (lowest c).
u = max (-ax, 03 Eisjen-1 xy[ for each I {0, 13"=1 and constants az Then, we prove that there exists constants aj such that NVxr) for all I by solving a linear system.
Relation PSI: Theorem 5.1 shows that there are exponentially large training sets that can be exactly fit with H. This fact can be used to show a lower bound sample complexity that is exponential in d for general ERM algorithms (Anthony & Bartlett 2009). The networks that fit these datasets are those defined by w (2), (1) PSI property. To see this, note that M (1) M7 (2) O, which implies that the left-hand sides of parts and 2 in the Definition 4.1 are infinite. Therefore, PSI is not satisfied for these networks.
easy to see that these networks do not satisfy the
These networks classify points based on the spurious patterns Ps. and not the patterns which determine the class. Networks that satisfy PSI are essentially the opposite: they classify a point mostly based on detectors for the patterns p1 and Pa and thus generalize well, show next.
PSI IMPLIES GOOD GENERALIZATION
In the previous section showed that general ERM algorithm for the class H. may need exponen- tially many training samples to get low test error. Here we show that any algorithm satisfying the PSI condition (see Definition 4.1) will have low-degree polynomial sample complexity, when patterns in P. are unbiased (i.e., E [yl (p, æ}] = 0 for P; E P.). Specifically, in the following theorem we show that such algorithm will have zero test enror w.h.p., given only O(P)) log((P)) training samples. Note that this also implies a sample complexity of O(d log( ()) since |P| $ d.
Theorem 6.1. Assume that satisfies the conditions in Section and EE [[ (p. x)] for all P; P.- Let A be learning algorithm which satisfies (lPc, with b,c 2 1. Then, if 300b2e² log(()),, with probability at least 1 1 8- p/a
A(S) has test erron.
We defer the proof to the supplementary but here we sketch the main argument. By the assumption E [ (p; é .x)]= and standard concentration of measure, |s:| should be small and therefore the detection ratios should be small by PSI. Then, by the key observation that small detection ratios imply perfect classification (e.g.. Eq. 3). the algorithm achieves zero test error with respect to D.
EMPIRICAL AND THEORETICAL EVIDENCE THAT SGD SATISFIES PSI
Empirical Analysis: Thus far we have established that the PSI property implies good general- ization. Here we provide empirical evidence that SGD indeed learns such models with overparam- eterized CNNs. We also provide a qualitative analysis that further confirms that the statistics of the We note that the 3 may be improved to arbitrary 7 > if we scale by log

---

Under review as a conference paper at ICLR 2021
patterns in the training set correlate with the detection ratios. Full details of the experiments provided in the supplementary.
We perform experiments with two distributions denoted by D. and Dec that satisfy the properties defined in Section 3 and such that E [y](p; E =)]
0 for all p, 6 P... Thus, given Theorem 6.1 PSI holds, good generalization will be implied. See Section E.2 for details the distributions.
Next, we show that PSI holds with small constants b and c which do not change the order of magni- tude of the bound in Theorem 6.1 i.e., b2 < 10 We trained neural network in setting with SGD as described in Section 3 We performed more than 1000 experiments with different parameter E.3 for details) and performed 10 experiments for each set of values for n, d, k and m. For each experiment, we set b = 2 and empirically calculated the lowest constant с which satisfies the PSI definition, which we denote by c². The formal definition of c* is given in Eq. 10 in the supplementary. Figure Ta shows that across all experiments, the value of c* is less than 1, i.e. 82 (c*)² < 10. We further checked how e varies with & for D Du,, d = 50 and n = 20. Figure Ib shows that c" is at most slightly correlated with & and has low value for large k.
values for n, d, k and (see Section
The intuition we described in Section suggests that there is positive correlation between (1)
M
and max ()) To test this, we experimented with a distribution which can vary the probability of a spurious pattern be selected and thus can control max (- ن (-2,0) Figure Ic clearly shows positive correlation between these quantities, strongly suggesting that the statistics of the patterns in
the training set govern the magnitude of the detection ratios. See Section E.5 for further details.
Theoretical Analysis in Simplified Setup: Here we show that PSI holds for setup of two training points, S {(x .)), -1)). We further assume that x and x have exactly the same patterns in P.. We analyze gradient descent with constant learning rate v cz. The following theorem shows that PSI holds with constants b and V18c, The proof analyzes the trajectory of gradient descent and is provided in Section F
Theorem 7.1. For a sufficiently small e, Tg Gn such that og << 1) and k poly (log d, t)) with probability least d' 8 gradient descent converges to a global minimum after T s O Cr.
1
iterations and the PSI condition sutisfied with b and c= /88
The theorem holds for overparameterized networks, which coincides with our empirical findings in Section 7 The theorem holds for sufficiently small initialization, and thus it is not in the same regime of NTK analysis where initialization is large (Woodworth et al., 2019 Chizat al., 2019).
8 EXPERIMENT ON MNIST
In this section report experiments on variant of MNIST (LeCun) 1998) and show that we can use our analysis to better understand the performance of overparameterized CNNs in this setting. Full details of the experiments
given in Section
Our PSI results thus far can be summarized informally as follows. In pattern detection problem, an algorithm has PSI bias if the dot product between discriminative pattern and its detector is large, and the dot product between a spurious pattern and its detector is low. Furthermore, the gap between these dot products increases with the train size and sufficiently large gap implies perfect accuracy. While our analysis required the patterns to be orthogonal, the above idea can work beyond the orthogonal case, as the experiment below shows.
We consider data generated as follows. Each data point consists of 9 randomly sampled MNIST images, where y one of the digits is randomly chosen to be of color blue and the rest
To empirically validate PSI and show that it implies good generalization. we could in principle show that the conditions of Theorem 6.1 hold empirically, ie.. there exist b, c and m such that m 3006 dd log (d) and PSI holds with constants 6, and high probability 1 - 6. However, as with most generalization results. the numerical value (including constants) results in large m which cannot be empirically tested. Instead, we show that b and do not change the order of magnitude of the hound.
7

---

Under review as a conference paper at ICLR 2021
/ 3 0
& 5
7 0 6
y=1
6 5 9
2 9 9
8
7 1 9 9 6 4
w((
6 37
3 2
7
5
0 0 2 4 3
y=-1
8 0 3
5 2 4
u
8 6
7
2 5 3
9
(8)
(b)
6
m 20
m 1000
(c)
Figure 2: Experiments on a variant MNIST. (a) Examples of data points. (b) Filters of CNN with k = 1 that perfectly classifies the data (c) Examples of learned filters of overparameterized CNNs for different training set sizes. Figures of all learned filters are given in Section G
digits colored green. For y -1 similar sampling procedure is performed but with the color red instead of blue. Figure 2a shows examples of data points (note that in our notation n = 9 and d 28 28* 2352). Thus in this setting, red and blue digits discriminative whereas green are spurious.
We use the network in Eq. T and SGD to learn classifier for this data. The data be perfectly classified with a network with = 1 (see Figure We train an overparameterized network with = for different training sizes. Figure 2c shows subsets of the learned filters (see Section for all filters), for different training set sizes. The figures show in color the positive weight filter entries. The pattern that appears is the pattern that maximally activates them, i.c., the pattern they detect.
First, we can see that the filters come in three colors (blue, red, green) corresponding to the three pattern types they detect (positive, negative, spurious respectively). This fact is not trivial and is similar what we obtained in the proof of Theorem 7.I and explained Section
As noted above, the PSI prediction is that the dot product between detectors and detected patterns would be large for discriminative patterns (i.e., and blue) and low for spurious (i.e., green). Furthermore, this difference should increase with the data size m. Indeed, Figure[c]shooss precisely this behavior. Namely, as we increase the training set size, the green pattern detectors become darker and thus have low dot product with detected pattern. In contrast, the red and blue maintain a bright color and thus have large dot products with detected patterns. Finally, the test accuracy for 6, 20, 1000 is 88%. 100%, 100%, respectively. This is in line with Theorem 6. that shows PSI can lead to perfect test accuracy when the gap between dot products is sufficiently large.
CONCLUSIONS
Understanding the inductive bias of gradient methods for deep learning is an important challenge. In this paper, study the inductive bias of overparameterized CNNs in novel setup and provide
8

---

Under review as a conference paper at ICLR 2021
theoretical and empirical support that SGD exhibits good generalization performance. Our results on MNIST suggest that the PSI phenomenon goes beyond orthogonal patterns.
We unique approach of combining novel empirical observations with theoretical guarantees to make headway in a challenging setting of overparameterized CNNs. We believe that our work can pave the way for studying inductive bias of neural networks in other challenging settings.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization overparameter- ized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6155-6166, 2019.
Martin Anthony and Peter L Bartlett. Neural network learning: (eeooetiial cambridge university press, 2009.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pp. 7411-7422, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332, 2019b.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International Conference on Machine Learning, pp. 605-6144 2017.
Alon Brutzkus and Amir Globerson. Why do larger models generalize better? theoretical per- spective via the xor problem. In International Conference on Machine Learning, pp. 822-830-00 2019.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. International Con- ference on Learning Representations, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04440 04486, 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pp. 2933-2943, 2019.
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent leams one-hidden--ayer cnn: Don't 't be afraid of spurious local minima. In International Conference on Machine Learning, pp. 1339-1348, 2018a.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019.
Simon Du, Jason D Lee, and Yuandong Tian. When is convolutional filter easy to learn? ICLR, 2018b.
Simon S Du, Yining Wang. Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples are needed to estimate a convolutional neural network? In Advances in Neural Information Processing Systems, pp. 373-383, 2018c.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes werr-parameterized neural networks. International Conference Learning Representations, 2018d.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprint arXiv: 1008, 2017.

---

Under review as a conference paper at ICLR 2021
Jonathan Fiat, Eran Malach, and Shai Shalev-Shwarte Decoupling gating from linearity. arXiv preprint arXiv:1906.050:: 2019.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp- 9461-9471, 2018.
Ziwei Ji and Matus Telgarsky, Gradient descent aligns the layers of deep linear networks. ICLR, 2019.
Yiding Jiang. Behnam Neyshabur, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference on Learning Representations, 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Eyal Kushilevitz and Dan Roth. On learning visual concepts and dnf formulae. Machine Learning. 24(1):65-85, 1996.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprint arXiv: 2018.
Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. ICLR, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. ICLR, 2020.
Mor Shpigel Naeson, Suriya Gunasckar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference on Machine Learning, pp. 4683-4692, 2019.
Jack Sherman and Winifred Morrison. Adjustment of inverse matrix corresponding to change in one element of given matrix. The Annals of Mathematical Statistics, 21(1): 1950.
Haim Shvaytser. Learnable and nonlearnable visual concepts. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 12(5):55-466, 1990.
Yaniv Taigman, Ming Yang, Marc' Aurelio Ranzato, and Lior Wolf. Deepface: Closing the gap to human-leve performance face verification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1701-1708. 2014.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, pp. 9709-97211 2019.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. arXiv preprint (tfi::/906.08222.. 2019.
Kelvin Xu, Jimmy Ba. Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In International conference machine learning, pp. 2058-2057, 2015.
Bing Yu, Junzhao Zhang, and Zhanxing Zhu. On the learning dynamics of two-layer nonlinear convolutional neural networks. urXiv preprint arXiv: /905. 10157, (0157,2119) 2019.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.
Pan Zhou and Jiashi Feng. Understanding generalization and optimization performance of deep cnns. In International Conference on Machine Learning, pp. 5960-5969, 2018.
10

---

Under review as a conference paper at ICLR 2021
A VC DIMENSION UPPER BOUND
Without considering the order of the patterns in the images, there are at most (+) input points in D. Since the network in Eq.
invariant the order of the patterns in an image, this implies: VC(H) & (+) Note that for the definition of VC dimension, we assume that the domain of possible inputs is the domain of images of the distribution. This gives tighter upper bound for our problem.
B PROOF OF THEOREM 5.1
We will construct a set B of size 2n-1 2 that can be shattered. For a given E [0,1))-1 let [ be its jth entry. For any such define point æy such that for any S < n ær [[]Ppj-1 + +11 (1- (I-(())) Furthermore, arbitrarily choose æz [n] Pi or 21 [n] = P2 and define B {xx I (0.1))-1).
Now, assume that each point œ1 E B has label yı- We will show that there is network N e H such that N(x,) yr for all I. For each I E {0, 1)=11, define w( max (ar, 0} Eisjsn-1 27 [i] and (1) max {-ar, 0} Eisjen-r [i] where {aı} is the unique solution of the following linear system with 2 equations. For each {0, 1) "-1 the system has the following equation:
Σ
a1=yy-
PE(0.1]=-1M41)
where for any / {0,1)*-1 1" (0,1) defined such that [']]] 1 [[j] for all 1 S i There is a unique solution because the corresponding matrix of the linear system is the difference between an all I's matrix and the identity matrix. By the Aierman--Morrise formula (Sherman & Morrison 1950), this matrix is invertible, where in the formula the outer product rank-1 matrix is the all I's matrix and the invertible matrix is minus the identity matrix. Then for N with the above weights and any xy!
N(x))= = Σ max fo fo (w(())x(())) =m[1))] max fo (onxfo(uu)) [x]))= =[]])}]
re(0.1)m--1
( Σ ærli 0000)
Σ Or max
Σ ar 1/1
1e(0,1)=-1
3
Issisn-1
re(0.11=-1<(19)
by the definition of N, the orthogonality of the patterns, and Eq. F We have shown that any labeling yr can be achieved, and hence the set is shattered, completing the proof.
C PROOF OF THEOREM 6.1
WLOG we prove the theorem for [P| d. By the assumption, for p; Pa, is an average of m IID binary variables yj Lip æz with zero expected value. Thus, by Hoeffding's inequality we have for all P, that:
log(d) m
2 de
P
blsd
40
Therefore, by union bound over all patterns P; E P., with probability at least 1- 2 for all p, P,:
log(d) d)
b/sal 4b
(8)
6od
Next we consider P1 (the positive pattern), for which [[s]] = 0.5 (because only appears in the positive examples, and the prior over y is 0.5). Hoeffding 's bound and the definition of m imply that [s1] 2 3 with probability at least
IIn fact can have exponential dependence here, but we d simplify later expressions.
11

---

Under review as a conference paper at ICLR 2021
0.10
0.05
0.00
100
50000
100000
m
Figure 3: o² as function of the training set size m.
We can now do a union bound over all patterns and PSI condition obtain that with probability least 1 - 5 da we have by the PSI property and Eq. for all P; é P.:
(i)
$ b [scl
M (1)
88
Vm
2cd
Vm" d
From PSI have (1)
Therefore, for any positive point (x=,1) Eq. implies:
(1)
mm
Nw (x (1) (1 ---11
Thus, x" classified correctly. By the symmetry of the problem and part Definition 4.1 any negative point will be classified correctly as well.
D FURTHER EXPERIMENTS FOR VALIDATION OF PSI
To further validate the PSI condition, we tested whether the conditions in the proof of Theorem 6.1
empirically hold. Specifically, in the proof we showed that (+) M1)1) for all p; P, (in Eq. 9). We
checked this for all settings of (n,d) and largest possible l and m, k 10000 and 40000. In
all of our experiments, SGD converged to a solution with test error such that Eq. holds for all P, P..
Finally, we checked how varies with m. Figure 3 show that e* most slightly cor- related with m and has low value for large In the same setup of Section E.3] performed experiments with distribution Du. n 20, d = 50, k 2500 and m (100, 200, 500, 1000, 2000, 5000, 20000, 40000, 80000, 120000).
E EXPERIMENTAL DETAILS OF SECTION
Here we provide details of the experiments performed in Section All experiments were run on NVidia Titan Xp GPUs with 12GB memory. Training algorithms were implemented Tensor- Flow. All of the empirical results can be replicated in approximately 150 hours on single Nvidia Titan Xp GPU.
E.
VALUE OF
We the following formula to compute e* in the experiments:
Mi(1)
8;
MT dEP M2
- (- (10)
m max
max
mmxx
max
2 max
UPP M1
81
E.2 DISTRIBUTIONS IN EXPERIMENTS
We perform experiments with two types of distributions that satisfy the propertics defined in Section
They differ in the random sampling procedure of spurious patterns described in Section 3 In both
12

---

Under review as a conference paper at ICLR 2021
y=1
-=-1
P+
P_
P
Figure 4: Example of points in orthogonal patterns distribution. Here there are 25 possible orthogonal patterns (iPl = 25) and each pattern is a 10 x 10 image patch and thus d = 100. The number of patterns in each image is n 16. The image consists of rows of 4 patches each. The positive examples contain the pattern in P.. The negative examples contain the pattern in P_. In the leftmost images of each class, the corresponding pattern is shown, All other patterns in an image are from the set of spurious patterns P.
set of all one-hot vectors in Rd. In the first distribution D.. the n spurious patterns selected uniformly random without replacement from P.. In the second distribution Dr., for each 1 j n 1 one of the patterns from (P2j+1: P2j+2] is selected uniformly at random. Importantly, both D., and Due satisfy E [yl (p, xx} = for all p; P.. Thus, given Theorem 6.1 PSI holds, good generalization will be implied.
distributions
Remark E.1. The support of Dee is the shallered set B in the proof of Theorem 5.1 The proof implies that for any sampled training and test sets which are subsets of B, there exists a network with 0 training error and arbitrarily high test error. Therefore, by optimizing the training error, SGD can converge to these solutions. However, as we show empirically, SGD does not converge these solutions, but rather it satisfies PSI and converges solutions with good generalization performance.
E.3 FIGURE LA EXPERIMENT
We performed more than 1000 experiments with the network in Eq. and SGD. We experimented with parameter values
{1000, 10000), m (100, 500, 1000, 2000, 5000, 20000, 40000) (n,d) e ((10, 20), (10, 80), (20, 50), (40,60) 60)) for D ((10, 20), (40, (25, 50), (30, 60)} for D Doc. For each distribution Du or Dve. we performed 10 experiments for each set of values for n, d, k and m. For each set of values we plot the mean of the 10 experiments and standard deviation error bars shaded regions. In each one of the 10 experiments we randomly sampled the training and test sets according to the given distribution D. or D..e and randomly sampled the initialization set of size 1000. All orthogonal patterns were one-hot vectors. We trained only the weights of the first convolutional layer. We used a batch size of 20 k 1000. The learning rate set to max{ 0.001
D. and (n.d) e
the network. We used a test
10000 and batch size of 100 for 24 0.0000001) and o, 0.000001. The solution SGD returned was either after 50000 epochs or there was an epoch where the training loss was less than 0.00001. For each experiment, set 2 and empirically calculated c².
13

---

Under review as a conference paper at ICLR 2021
E.4 FIGURE BB EXPERIMENT
In the same setup of Section E.3 (i.e., batch size, stopping criteria, learning rate etc.), we performed experiments with distribution Du.
20, d 50, m 2000 and k.
{50, 100, 2500, 5000, 7500, 10000}.
E.5 FIGURE IC EXPERIMENT
We experimented with a distribution Dp which can vary the probability of spurious pattern to be selected and thus control max .)) Given y 1 it selects P3 with probability p Pa with probability 1-2 Then it selects the remaining n 2 patterns from P, (Ps.PA uniformly random without replacement. Similarly, given y =1 it selects P3 with probability 1 1-p p or P4 with probability p. The remaining n 2 patterns are selected uniformly without replacement from
P. (Ps.Pa) We experimented with various p and plotted for each solution of SGD, M and MC(1)
max (- for all p; P, P.P
In the setup of Section
we experimented with distributions D, for p values
{0.0, 0.01 0.03, 0.05, 0.07, (0000000000000000000000000000221 0.28 0.3, 0.4,
0.7, 0.78, 0.8, 0.9, 0,9, 0.44, 0.5, 0.51, 0.59, 0.6,,,99,,00..... 07,
0.95, 0.98, 0.99,
We experimented with values 40, d = 60, 1000 and l: 2500. The solution SGD returned was either after 2000 epochs or there was an epoch where the training loss was less than 0.00001.
F PROOF OF THEOREM 7.1
F.1 NOTATIONS
Here define additional notations that will be usefuul for the proof the theorem.
Let Pr be the set of all patterns that appear in either x* or x" Similarly to Eq. define:
(1(
(1) j arg max wi PP =i-=i, w/ P, > (ePr>12)
(t)1) - arg max u. 1cPr>(2)
(
Pr i, u ())
p:
(11)
and
(1)
1 arg max w. ( (1)
: ip w( .p.> 0
(1) = arg max ui Pt u (eP
(
())
P; P 0
(12)
Define:
Aw U (i(1) (ePrN(2)
A, U (T sEPrx(1) (1)
Finally define poly(x)) to be any polynomial function of
14

---

Under review as a conference paper at ICLR 2021
F.2 AUXILIARY LEMMAS
We now prove several technical lemmas. In Section F.3 we use the lemmas to prove the theorem. In the next lemmas we provide high probability bounds on sizes of certain sets that are functions of the sets in Eq. IT and Eq. 12
Lemma F.1. For any 0 <<<< < 3. with probability at least 1 - -e for any k > poly :
Awwl
se
k:
and
|Aul
- 2-
Se
k
Proof. It suffices show that for any k:
|| (1-2 1|| 22
and
- (1-1-(1-27)) k|
each 1 S s htlds that je E Aw with probability 1-2- Therefore by Hoeffding's inequality, with probability at least 1 -8-8
A 2
-
The same argument applies for |uu) union bound and setting k > 2 concludes the proof.
Lemma F.2. For any with probability at least $ 4c for k poly(log :) and for all i Pr (2):
(W)
1
+c
(1-2-H + n
and
(W((1)
-
k (1 - -1-2-" -2)
Similarly, for all i Pr (1):
(45 (1)
1
5
- 2 (1-2-* +c)
n
and
(45
1
2 -
(1-22n
Proof. Without loss of generality, consider 1W (i)). We first condition on the random variable A and given that the event 1<1 - 2-n Auwl ks1 2-n +c holds. By symmetry, have ( Mw
where the expectation with respect to the initialization. Thus, we get by
Hoeffding's 's inequality:
[ (1)
2
AAwl
[Aw
2/
2u/wax ViAw!
2e
dB
By the law of total probability, applying Lemma F.I and a union bound over i Pr twice (for both Wi (i) and un (i)), get the desired result.
15

---

Under review as a conference paper at ICLR 2021
Lemma F.3. For any with probability at least 1 t -c % for k poly(logd, +) and for
all i Pr (1,2) the following holds:
( n (2)
1
k k ((=-2-=1+c)
n(n+1)
1
k(3- -
n(n+ +
(1)
k ( 2(2-2--1++ +c)
n(n+ 1)
and
[ (1) n2, k { 2 -c
n(n+ 1)
Proof. The proof is similar to the proofs of Lemma and Lemma F.2 The difference is that we use the equalities E [] n Wo (2)]] = E B[ Un (1)ll
g-n-1) instead of
[[Aw]]] [[AAll] (1-2-") as in Lemma E1 Furthermore, we use
Mw (2)
(+(
(t)
[Aur(T(() nnn+1) for fixed A Wo (2) and |Au n n6 (1)l instead of E
|Aul
(i) 1 for fixed |A and Aul as in Lemma F2
[Au
Lemma F4. For any M > 0 and 8 > O, there exists a sufficiently small 0g > 0, such that with probability least for all i k 100 s and un S. M.
Proof. The proof is immediate.
L
We now proceed to analyze the dynamics gradient descent in the next two lemmas. Define M such that for all i S k, (3) M and un s M. Let & be the set of all such that for all x e S.S it holds that Nw, (ax) < 1. Let arg min, (t- 1 E t E). We assume that v) and og are sufficiently small such that t* 2 2.
Lemma F.5. For sufficiently small e, M, on such that M << n, the following holds for any 1stst:
1. Ifj é Aw, then w = = (1)
-a
where a 1).
2. Ifj (1), then w (1) = (
w
at " EiE (1) osp; 2 Pr. where as (0,1).
3. if Pr and j Wt (1) W (i) then w =
4. ifi Prop, and E Wt (1) n (2). then u w 22 3p.
5. Ifj é An then u. =u ap, where (0,1).
(j)
6. fʃj e Up (2), then u. uo (1) Eiery> o:p; + P2 where as (0, 1}.
7. ifi Prop, and j Ut (1) 2 (1) then u un
(1) (i)
8. Ifie ProP, and j u, (1) n6 (1), then ut = u p + T.
(i)
Proof.
the gradient of the loss with respect to w(()) is O. because every pattern in Pr has a negative dot product with w Therefore, w = w (1) By the same argument w.S² ( ( for all 1. If Wj (2) then HP, will subtracted in the first iteration, and un (t) will not change in later iterations.
1. If (2), then for
16

---

Under review as a conference paper at ICLR 2021
2. The proof follows directly by the gradient update. In each iteration, YP is added and pattern in Pr> } is subtracted unless all such patterns already have a negative dot product with wi (6) Note that we used here the fact that M << 1
3. For t = we have by the gradient update:
w w
17 p pP:
"
= =w ())
(i)
(13)
(5) By induction, w. w for all 1stst.
4. The proof follows by the gradient update as in previous proofs. For t = 1, the term 3p2 is subtracted by the update of x² since j Wi (2). The term 3p, is added due to the update of x². Now je Wi (1) n WI()) and thus w will not change in subsequent iterations, as in the proof of part 3. This concludes the proof.
By symmetry, the proofs of 5-8 are identical the proofs of parts 1-4.
Define
y= (1-2-a)
(14)
then we have the following:
Lemma F.6. For sufficientll small e, M, on such that M << yj and k 2 poly (log d, 2) with probability at least 1 y
di S gradient descent converges to a global minimum after s yyn
3. iterations.
76,
Proof. Throughout the proof we use Lemma F.4 to choose a sufficiently small M such that w
M and ug $ .M with probablity at least d We further apply Lemma F.1
Lemma
F22
and
Lemma F33 which together with Lemma R.4 hold with probability at least
Se
Define the
sets of weights B; such that i corresponds to the set of weights in part of Lemma
F.5
For example,
B3 = Wi (1) and Bg = UieP Ug (i) n2] (1).
Define the following:
((1)) (x) (x) = Σ max for .u()));)))
B, )
N:22 Σ
max fo (u()),)))) .;))
W/
ieB $
(23) (x) = Σ W.
max for (t) .,)))))))))))))))))))))))))).. x;1}}
B
Σ
max o (u (i) xz,))
Bs
and
(x) Nw. - x1(1) (x) NT(2) (x)) N1(3) (a)
Σ max (o (t) 22)]
iBBuuB
Σ max for (z) .z,)]
BBB, j
We would like analyze the dynamics of Nw, (x*). To do so, we will address each 1: (xx) in turn for 1 < i t".
17

---

Under review as a conference paper at ICLR 2021
Bounding N/T, (x"): By Lemma F.5 part it follows that N
(ar
Ejenz w
S.4laal for
all 1 stsss t² Recall the definition of y i Eq. 14 Then, by Lemma poly(logd, 2) holds that:
for sufficiently small and
B2l
? c
By Lemma F4
we have:
Σ B2
wp
s B2 M s (7k ek)
Therefore, after s $ 1" iterations, we have:
Cr W. (x
Cgty 2
s (kk + G 2
By choosing M and to be sufficiently small (given an upper bound on / that does not depend on M and e, which we show later), [ (x*)
Satz is sufficiently small.
2
Calculating N (a=)): Notice that after iterations, have by Lemma F.5 part that
N (x*) 0. By taking Cy to be sufficiently small, we can ensure that n - l<tt.
Bounding N (x"):
By Lemma F.5 parts and 8 and given that M << on have for 1 1stst.
(r(3)
(x+)=
On
Σ
(2))) Σ (6(())
2k
inP
iePrPP
By Lemma for sufficiently small for any i Pr n P., the difference
F3
(WW (2) M4 (1) (z)
is sufficiently small. We conclude that (3(3) Ww (x*) is sufficiently small for small e.
Bounding (4) W. (x*): By Lemma F.5 parts 1,3,5,7 it follows that
(x(4) W. (x") ) kM
and thus can be made sufficienlly small for small M.
Finishing the proof: By combining the previous arguments we have
Nw. (a+) = C
2 + g+
for 1 1stst. t", where 3+ is sufficiently small.
By symmetry, we have:
Cyty 2 + g
-Nw, (a
18

---

Under review as a conference paper at ICLR 2021
for 1 ssts t", where 8 is sufficiently small.
Our goal is to show that gradient converges to a global minimum at T t². Let
G
t* arg min ast
2 + 8* >
and
Cpll 2
arg min
+ + 3x111
age
where the minimum over integral times t. Notice that to! t can only oceur when there exists an integer such that
S max
(15)
2
Choose Cy to be small number which is not integral multiple of (e.g., choose irrational Gy)) Then, max { {8") can be made sufficiently small such that Eq. 15 does not hold. In this case, iterations, gradient descent converges to global minimum.
after 1 $ Et = t = s yo y0u
F.3 FINISHING THE PROOF OF THEOREM
We ready to prove the theorem. Gradient descent converges global minimum after Furthermore, by the proof of Lemma F.6 (1)
$ T 3. iterations by Lemma F.6
( W (1). For each j W (1), the norm of w is least 2 2, Therefore, for sufficiently
small by Lemma F2
(L 27k
M (1)
Now, by Lemma F.6 for all j$ W (1), holds that (w
S w n q.. Therefore, for
all P (2), M.r (1) Cx- By symmetry, it follows that the PSI property holds with 1 and == /18c.-
G EXPERIMENTAL DETAILS OF SECTION g
Here provide details of the experiments performed in Section All experiments NVidia Titan Xp GPUs with 12GB of memory. Training algorithms were implemented in Py All of the empirical results can be replicated in approximately one hour single Nvidia Titan Xp GPU.
We now describe how we created train and test for our setting, For train we sampled digits from the original MNIST training set and for test we sampled digits from the original MNIST test set. To sample data point, we randomly sampled label (+1). Then, if y 1 randomly sampled 9 MNIST digits (either from the MNIST train or test set). Then randomly chose 8 of them to be the color green and one of them to be the color blue. If 1, we do the same procedure with blue replaced by red.
For training we implemented the setting in Section 3 Specifically, here we have n 9 and 28 28 * 3 2352. We trained the network in Eq. with k = 20 for training set sizes m 6, m 20 and m 1000. For each training set size we performed 10 different experiments with different sampled training set and initialization. We ran SGD with batch size min m), learning rate 0.0001 and for 200 epochs. We report the test accuracy and train accuracy in the final epoch (200). In all runs SGD gets 100% train accuracy. For 6 the mean test accuracy is 88.09% with standard deviation 12.7, for m 20 the mean test accuracy is 99,88 99,84% with standard deviation 0.35 and for m 1000 the mean test accuracy is 100% with standard deviation 0.
Figure Figure 6 and Figure show the set of all filters the experiments reported in Figure 2c for 6, m 20 and 1000, respectively. To plot the figures, for each entry of the filter
Note that max (88', , } does not depend on Cq.
19

---

Under review as a conference paper at ICLR 2021
Figure 5: Learned filters for experiment with m = 6.
Figure 6: Learned filters for experiment with m = 20.
we calculated max(0, 3.). We scaled the weights of the network to be with values between 0 to 255 by dividing all entries by the maximum entry across all parameters of the network (after performing max 2r)) and multiplying by 255.
20

---

Under review as a conference paper at ICLR 2021
Figure 7: Learned filters for experiment with 1000.
21


Reviews:
[{"review_id": "qKuFoCPZQ8Y", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is concerned with the question of generalization of convolutional neural networks. For that, the authors study a simple toy model, where each data point consists of several patterns. All patterns are assumed to be orthogonal to each other. Those images should be learned with a 3-layer neural network. The contributions of this paper are as follows:\n\n1. The authors show that the networks, which are analyzed in this paper, have large VC dimension. In particular, this implies that generalization cannot be explained via generic VC theory. \n2. As a way out, the authors introduce the concept of Patterns Statistics Inductive Bias (PSI). This relates the weight to the patterns in the dataset. In particular, the authors prove that PSI implies good generalization.\n3. The authors study the conjecture, that training a neural network via gradient descent (with hinge loss) leads to a network, which satisfies the (PSI) condition.  They provide empirical as well as some theoretical evidence.\n\nI think this is an interesting paper, which develops a new point of view and contains interesting ideas. While, the paper does not provide full evidence that the (PSI) condition is the right way to look at the problem, it may open up a new research direction.\n\nOn a personal level, I think point 1. and 2. are argued convincingly in the paper, but 3. could be strengthened with more evidence. For example, Theorem 7.1 allows for only two data points. It would be interesting to see a more general version of this theorem.\n\nRemarks:\n-I was wondering about Figure 1c). What happens, if you increase $\\max (0, \\frac{s_i}{s_1}) $ above $1$?\n-Why do you choose $b=2$ for the experiments in Section 7?\n\n\nSome typos:\n-p. 6 Figure 1c): It should be $\\max (0, \\frac{s_i}{s_1}) $.\n\n--------------------------------\nI want to thank the authors for their rebuttal. I will stick to my decision and not change the score.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "llWYmqvYxsO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied a simplified image classification task with orthogonal non-overlapping patches and is learned by a 3-layer CNN. The authors observed pattern statics inductive bias (PSI) in experiments. They proved that if a learning algorithm satisfies PSI, the sample complexity is nearly quadratic in the filter dimension; while the VC dimension of the network is at least exponential in the filter dimension. The authors also verified PSI in some task based on MNIST that has non-orthogonal patches.\n\nMy major concern about this paper is that the theory seems to only work under orthogonal patterns and non-overlapping filters, unfortunately, neither of which is true in practice. So it’s unclear if this theory can explain the success of CNN in practice. I also have other concerns:\n1. This is mainly a theory paper, but the theoretical contribution is pretty limited. The theory only considers orthogonal patterns and non-overlapping filters. Theorem 6.1 needs to assume that PSI holds and spurious patterns are unbiased; under these assumptions, the result is pretty straightforward. This paper didn’t prove PSI holds for SGD except in a toy example (two training points).\n2. The lower bound on the VC dimension is only exponential in the filter size. This lower bound is pretty weak since in practice the filter size is usually small (e.g. 3x3).\n3. The experiment is run on an artificial task based on MNIST images. It would be much more convincing if the experiment is on standard tasks (like 10-class classification in MNIST). Since the theoretical setting is limited, it needs experiments to show how the theory applies to practical tasks. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "bWaBmccdDDQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this manuscript the authors derive theoretical analysis for the generalization guarantees of a naïve CNN (3-layers) where the task is a simplified binary classification task, under the assumption that the images contain orthogonal patches (a naïve assumption). They define a statistical phenomenon that holds in SGD in the proposed setting and call it Pattern Statistics Inductive Bias (PSI). Informally, this means that the magnitude of the dot-product between the learned pattern detectors and their detected patterns is correlated with the distribution of the patterns in the data.   They prove that if a learning algorithm  satisfies PSI then its sample complexity is O(d^2 log (d)), where d is the dimension of the filter. According to their empirical derivation SGD satisfies this property. In contrast there exist learning algorithms that have exponential sample complexity. \n\nPros.\n1.\tAddressing the problem of generalization guarantees is important and interesting.   \n2.\tNovelty. In some sense, this works shows theoretical results which are less restrictive than Yu at el, circumventing the dependence of the sample complexity on the network size. \n3.\tAlthough the setting presented in this manuscript is quite limited, empirical observations on MNIST are in line with the analysis. \n\nCons.\n1.\tIt is not easy / straightforward to follow the manuscript.\n2.\tSpecifically, the intuition, given in Sec. 4, is not clear.  \n3.\tThe proposed setting, which assumes orthogonal patches in images, is very limited and not natural.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9J7ST3q2a5", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a new theoretical framework to understand the ability of \nConvNets to deal with pattern recognition tasks. The authors suggest a new property \nof convents where filters have large dot products with patterns occurring in images classified as 1 and small dot products with patterns appearing with images classified as 0. \nIt is assumed that there are two unique patterns whose occurrence in an image determines if the image is classified by 1 or 0. \n\nI like the classification problem studied in the paper and the attempt to understand how ConvNets work from first principles.  \n\nMy issue with this paper is that it uses rather cumbersome measures (PSI and detection ratios). The setting is very specific (one type of architecture, realizability assumption, a single positive pattern and a single negative one). \nThe combination of these factors casts doubts on whether these measures and analysis will be of any use elsewhere.  The authors claim: \n\n\"Empirically, we identify a novel property of the solutions found by SGD. We observe that the statistics of patterns in the training data govern \nthe magnitude of the dot-product between learned pattern detectors and their detected patterns. Specifically, patterns that appear almost exclusively in one of the classes will have a large dot-product with the channels that detect them. On the other hand, patterns that appear roughly equally in both \nclasses, will have a low dot-product with their detecting channels. We formally define this as the “Pattern Statistics Inductive Bias” condition (PSI) and \nprovide empirical evidence that PSI holds across a large number of instances. We also prove that SGD indeed satisfies PSI in a simple setup of two points in the training set\" \n\nI find this somewhat unsatisfying. The novel property mentioned by the authors is one of the first that comes to mind when thinking about the success of ConvNets. It seems very \nunlikely that this has not been observed before (at least empirically). While obtaining rigorous proofs of properties of NN is hard, one would expect that for the simple setting studied \nby the authors there would be a simpler explanation for the so-called PSI. \n\nThis paper makes numerous restrictions and assumptions. \nSome examples: \n\n\"a natural model in this context is a 3-layer network with a convolutional layer, followed by ReLU, max pooling and a fully-connected layer.\"\nWhy is this a natural architecture? Has it been studied before or used before? \nAlso in the classification task why is it assumed that n<d? \n\nThere are many more such examples. \n\nThe proof of Theorem 5.1 uses the Sherman-Morrison formula without giving the formula and showing how it is used. \n\nThe survey of related work is very short, not mentioning many relevant works looking into similar pattern recognition problems. \n\nSome examples:\nLearnable and Nonlearnable Visual Concepts (Shvayster, 1990)On learning visual concepts and DNF formulae (Kushilevitz, Roth, 1996)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers a new model of input data specific for image classification problems. In particular, the high level idea is that each image contains certain patterns, and which patterns it contain decides its label. In this framework, under some stronger assumptions (e.g., patterns are orthogonal, one positive pattern and one negative pattern, PSI assumption, etc.) the authors showed that SGD on a 3-layer overparametrized convolutional network will be able to have a small sample complexity, while the VC dimension would be at least exponential in d. The paper also provided some empirical evidence on a modified MNIST dataset. While the idea seems to be an interesting first step, the reviewers find that the current version of theory still relies on fairly strong assumptions.
Decision: Reject