Title: OVER-PARAMETERIZATION IMPROVES GENERALIZA-TION IN THE XOR DETECTION PROBLEM

Abstract: Empirical evidence suggests that neural networks with ReLU activations generalize better with over-parameterization. However, there is currently no theoretical analysis that explains this observation. In this work, we study a simplified learning task with over-parameterized convolutional networks that empirically exhibits the same qualitative phenomenon. For this setting, we provide a theoretical analysis of the optimization and generalization performance of gradient descent. Specifically, we prove data-dependent sample complexity bounds which show that overparameterization improves the generalization performance of gradient descent.
Learning Setup: Our analysis will focus on the problem of learning f * from training data with a three layer neural net model. The learning algorithm will be gradient descent, randomly initialized. As in any learning task in practice, f * is unknown to the training algorithm. Our goal is to analyze the performance of gradient descent when given data that is labeled with f * . We assume that we are given a training set S = S + ∪ S -⊆ {±1} 2d × {±1} 2 where S + consists of m IID points drawn from D + and S -consists of m IID points drawn from D -. 3 

1. INTRODUCTION:

Most successful deep learning models use a number of parameters that is larger than the number of parameters that are needed to get zero-training error. This is typically referred to as overparameterization. Indeed, it can be argued that over-parameterization is one of the key techniques that has led to the remarkable success of neural networks. However, there is still no theoretical account for its effectiveness.

One very intriguing observation in this context is that over-parameterized networks with ReLU activations, which are trained with gradient based methods, often exhibit better generalization error than smaller networks (Neyshabur et al., 2014; 2018; Novak et al., 2018) . This somewhat counterintuitive observation suggests that first-order methods which are trained on over-parameterized networks have an inductive bias towards solutions with better generalization performance. Understanding this inductive bias is a necessary step towards a full understanding of neural networks in practice.

Providing theoretical guarantees for this phenomenon is extremely challenging due to two main reasons. First, to show a generalization gap, one needs to prove that large networks have better sample complexity than smaller ones. However, current generalization bounds that are based on complexity measures do not offer such guarantees. Second, analyzing the dynamics of first-order methods on networks with ReLU activations is a major challenge. Indeed, there do not exist optimization guarantees even for simple learning tasks such as the classic XOR problem in two dimensions. 1 To advance this issue, we focus on a particular learning setting that captures key properties of the over-parameterization phenomenon. We consider a high-dimensional extension of the XOR problem, which we refer to as the "XOR Detection problem (XORD)". The XORD is a pattern recognition task where the goal is to learn a function which classifies binary vectors according to whether they contain a two-dimensional binary XOR pattern (i.e., (1, 1) or (-1, -1)). This problem contains the classic XOR problem as a special case when the vectors are two dimensional. We consider learning this function with gradient descent trained on an over-parameterized convolutional neural network (i.e., with multiple channels) with ReLU activations and three layers: convolutional, max pooling and fully connected. As can be seen in Fig. 1 , over-parameterization improves generalization in this problem as well. Therefore it serves as a good test-bed for understanding the role of over-parameterization. 1 We are referring to the problem of learning the XOR function given four two-dimensional points with binary entries, using a moderate size one-hidden layer neural network (e.g., with 50 hidden neurons). Note that there are no optimization guarantees for this setting. Variants of XOR have been studied in Lisboa & Perantonis (1991) ; Sprinkhuizen-Kuyper & Boers (1998) but these works only analyzed the optimization landscape and did not provide guarantees for optimization methods. We provide guarantees for this problem in Sec. 9. . In this work we provide an analysis of optimization and generalization of gradient descent for XORD. We show that for various input distributions, ranges of accuracy and confidence parameters, sufficiently over-parameterized networks have better sample complexity than a small network which can realize the ground truth classifier. To the best of our knowledge, this is the first example which shows that over-paramaterization can provably improve generalization for a neural network with ReLU activations.

Our analysis provides a clear distinction between the inductive bias of gradient descent for overparameterized and small networks. It reveals that over-parameterized networks are biased towards global minima that detect more patterns in the data than global minima found by small networks.2 Thus, even though both networks succeed in optimization, the larger one has better generalization performance. We provide experiments which show that the same phenomenon occurs in a more general setting with more patterns in the data and non-binary input. We further show that our analysis can predict the behavior of over-parameterized networks trained on MNIST and guide a compression scheme for over-parameterized networks with a mild loss in accuracy (Sec. 6).

2. RELATED WORK:

In recent years there have been many works on theoretical aspects of deep learning. We will refer to those that are most relevant to this work. First, we note that we are not aware of any work that shows that generalization performance provably improves with over-parameterization. This distinguishes our work from all previous works.

Several works study convolutional networks with ReLU activations and their properties (Du et al., 2017a; b; Brutzkus & Globerson, 2017) . All of these works consider convolutional networks with a single channel. Daniely (2017) and Li & Liang (2018) provide guarantees for SGD in general settings. However, their analysis holds for over-parameterized networks with an extremely large number of neurons that are not used in practice (e.g., the number of neurons is a very large polynomial of certain problem parameters). Furthermore, we consider a 3-layer convolutional network with max-pooling which is not studied in these works. Soltanolkotabi et al. (2018) , Du & Lee (2018) and Li et al. (2017) study the role of overparameterization in the case of quadratic activation functions. Brutzkus et al. (2018) provide generalization guarantees for over-parameterized networks with Leaky ReLU activations on linearly separable data. Neyshabur et al. (2018) prove generalization bounds for neural networks. However, these bounds are empirically vacuous for over-parameterized networks and they do not prove that networks found by optimization algorithms give low generalization bounds.

We begin with some notations and definitions. Let d ≥ 4 be an integer. We consider a classification problem in the space {±1} 2d . Namely, the space of vectors of 2d coordinates where each coordinate can be +1 or -1. Given a vector x ∈ {±1} 2d , we consider its partition into d sets of two coordinates as follows x = (x 1 , ..., x d ) where x i ∈ {±1} 2 . We refer to each such x i as a pattern in x.

Neural Architecture: We consider learning with the following three-layer neural net model. The first layer is a convolutional layer with non-overlapping filters and multiple channels, the second layer is max pooling and the third layer is a fully connected layer with 2k hidden neurons and weights fixed to values ±1. Formally, for an input x = (x 1 , ..., x d ) ∈ R 2d where x i ∈ R 2 , the output of the network is given by:

N W (x) = k i=1 max j σ w (i) • x j -max j σ u (i) • x j (1)

where W ∈ R 2k×2 is the weight matrix whose rows are the w (i) vectors followed by the u (i) vectors, and σ(x) = max{0, x} is the ReLU activation applied element-wise. See Figure 4 for an illustration of this architecture. Remark 3.1. Because there are only 4 different patterns, the network is limited in terms of the number of different rules it can implement. Specifically, it is easy to show that its VC dimension is at most 15 (see Sec. 10). Despite this limited expressive power, there is a generalization gap between small and large networks in this setting, as can be seen in Figure 1 , and in our analysis below.

Data Generating Distribution: Next we define the classification rule we will focus on. Let P XOR correspond to the following two patterns: P XOR = {(1, 1), (-1, -1)}. Define the classification rule:

f * (x) = 1 ∃i ∈ {1, . . . , d} : x i ∈ P XOR -1 otherwise (2)

Namely, f * detects whether a pattern in P XOR appears in the input. In what follows, we refer to P XOR as the set of positive patterns and {±1} 2 \ P XOR as the set of negative patterns.

Let D be a distribution over X × {±1} such that for all (x, y) ∼ D we have y = f * (x). We say that a point (x, y) is positive if y = 1 and negative otherwise. Let D + be the marginal distribution over {±1} 2d of positive points and D -be the marginal distribution of negative points.

In the following definition we introduce the notion of diverse points, which will play a key role in our analysis. Definition 3.2 (Diverse Points). We say that a positive point (x, 1) is diverse if for all z ∈ {±1} 2 there exists 1 ≤ i ≤ d such that x i = z. We say that a negative point (x, -1) is diverse if for all z ∈ {±1} 2 \ P XOR there exists 1 ≤ i ≤ d such that x i = z.

For φ ∈ {-, +} define p φ to be the probability that x is diverse with respect to D φ . For example, if both D + and D -are uniform, then by the inclusion-exclusion principle it follows that

p + = 1 -4•3 d -6•2 d +4 4 d and p -= 1 -1 2 d-1 .

For each set of binary patterns A ⊆ {±1} 2 define p A to be the probability to sample a point which contains all patterns in A and no patterns in A c (the complement of A). Let A 1 = {2}, A 2 = {4}, A 3 = {2, 4, 1} and A 4 = {2, 4, 3}.The following quantity will be useful in our analysis:

p * = min 1≤i≤4 p Ai (3)

Importantly, we note that the function f * can be realized by the above network with k = 2. Indeed, the network N defined by the filters w (1) = (3, 3), w (2) = (-3, -3), u (1) = (-1, 1), u (2) = (1, -1) satisfies sign (N (x)) = f * (x) for all x ∈ {±1} 2d . It can be seen that for k = 1, f * cannot be realized. Therefore, any k > 2 is an over-parameterized setting.

Training Algorithm: We will use gradient descent to optimize the following hinge-loss function.

EQUATION

for γ ≥ 1. 4 We assume that gradient descent runs with a constant learning rate η and the weights are randomly initiliazed with IID Gaussian weights with mean 0 and standard deviation σ g . Furthermore, only the weights of the first layer, the convolutional filters, are trained.5 

We will need the following notation. Let W t be the weight matrix in iteration t of gradient descent.

For

1 ≤ i ≤ k, denote by w (i) t ∈ R 2 the ith convolutional filter at iteration t. Similarly, for 1 ≤ i ≤ k we define u (i)

t ∈ R 2 to be the k + i convolutional filter at iteration t. We assume that each w (i) 0 and u (i) 0 is initialized as a Gaussian random variable where the entries are IID and distributed as N (0, σ 2 g ). In each iteration, gradient descent performs the update

W t+1 = W t -η ∂ ∂W (W t ).

4. MAIN RESULT:

In this section we state our main result that demonstrates the generalization gap between overparameterized networks and networks with k = 2. Define the generalization error to be the difference between the 0-1 test error and the 0-1 training error. For any , δ and training algorithm let m( , δ) be the sample complexity of a training algorithm, namely, the number of minimal samples the algorithm needs to get at most generalization error with probability at least 1 -δ. We consider running gradient descent in two cases, when k ≥ 120 and k = 2. In the next section we exactly define under which set of parameters gradient descent runs, e.g., which constant learning rates.

Fix parameters p + and p -of a distribution D and denote by c < 10 -10 a negligible constant. Assume that gradient descent is given a sample of points drawn from D + and D -. We denote the sample complexity of gradient descent in the cases k ≥ 120 and k = 2, by m 1 and m 2 , respectively.

The following result shows a data dependent generalization gap (recall the definition of p * in Eq. 3). Theorem 4.1. Let D be a distribution with paramaters p + , p -and p * . Let

δ ≥ 1 -p + p -(1 -c - 16e -8 ) and 0 ≤ < p * . Then m 1 ( , δ) ≤ 2 whereas m 2 ( , δ) ≥ 2 log( 48δ 33(1-c) ) log(p+p-) . 6

The proof follows from Theorem 5.2 and Theorem 5.3 which we state in the next section. The proof is given in Sec. 8.8. One surprising fact of this theorem is that m 1 (0, δ) ≤ 2. Indeed, our analysis shows that for an over-parameterized network and for sufficiently large p + and p -, one diverse positive point and one diverse negative suffice for gradient descent to learn f * with high probability. We note that even in this case, the dynamics of gradient descent is highly complex. This is due to the randomness of the initialization and to the fact that there are multiple weight filters in the network, each with different dynamics. See Sec. 5 for further details.

We will illustrate the guarantee of Theorem 4.1 with several numerical examples. In all of the examples we assume that for the distribution D, the probability to sample a positive point is 1 2 and

p * = min 1-p+ 4 , 1-p- 4

(it is easy to constuct such distributions). In the first example, we assume that p + = p -= 0.98 and δ = 1 -0.98 2 (1 -c -16e -8 ) ≤ 0.05. In this case we get that for any 0 ≤ < 0.005, m 1 ( , δ) ≤ 2 whereas m 2 ( , δ) ≥ 129. For the second example consider the case where p + = p -= 0.92. It follows that for δ = 0.16 and any 0 ≤ < 0.02 it holds that m 1 ( , δ) ≤ 2 and m 2 ( , δ) ≥ 17.

For = 0 and any δ > 0, by setting p + and p -to be sufficiently close to 1, we can get an arbitrarily large gap between m 1 ( , δ) and m 2 ( , δ). In contrast, for sufficiently small p + and p -, e.g., in which p + , p -≤ 0.7, our bound does not guarantee a generalization gap.

5. PROOF SKETCH AND INSIGHTS:

In this section we sketch the proof of Theorem 4.1. The theorem follows from two theorems: Theorem 5.2 for over-parameterized networks and Theorem 5.3 for networks with k = 2. We formally show this in Sec. 8.8. In Sec. 5.1 we state Theorem 5.2 and outline its proof. In Sec. 5.2 we state Theorem 5.3 and shortly outline its proof. Finally, for completeness, in Sec. 9 we also provide a convergence guarantee for the XOR problem with inputs in {±1}, which in our setting is the case of d = 1. In what follows, we will need the following formal definition for a detection of a pattern by a network.

Definition 5.1. Let c d ≥ 0 be a constant. For each positive pattern v p define

D vp = k i=1 σ w (i) • v p and for each negative pattern v n define D vn = k i=1 σ u (i) • v n .

We say that a pattern v (positive or negative) is detected by the network

N W with confidence c d if D v > c d .

The above definition captures a desired property of a network, namely, that its filters which are connected with a positive coefficient in the last layer, have high correlation with the positive patterns and analogously for the remaining filters and negative patterns. We note however, that the condition in which a network detects all patterns is not equivalent to realizing the ground truth f * . The former can hold without the latter and vice versa.

Theorem 5.2 and Theorem 5.3 together imply a clear characterization of the different inductive biases of gradient descent in the case of small (k = 2) and over-parameterized networks. The characterization is that over-parameterized networks are biased towards global minima that detect all patterns in the data, whereas small networks with k = 2 are biased towards global minima that do not detect all patterns (see Definition 5.1). In Sec. 8.5 we show this empirically in the XORD problem and in a generalization of the XORD problem.

In the following sections we will need several notations. Define x 1 = (1, 1), x 2 = (1, -1), x 3 = (-1, -1), x 4 = (-1, 1) to be the four possible patterns in the data and the following sets:

EQUATION

We denote by x + a positive diverse point and x -a negative diverse point. Define the following sum:

S + t = j∈W + t (1)∪W + t (3) max σ w (j) • x + 1 , ..., σ w (j) • x + d

Finally, in all of the results in this section we will denote by c < 10 -10 a negligible constant.

5.1. SAMPLE COMPLEXITY UPPER BOUND FOR OVER-PARAMETERIZED NETWORKS:

The main result in this section is given by the following theorem. iterations, it converges to a global minimum which satisfies:

1. sign (N W T (x)) = f * (x) for all x ∈ {±1} 2d . 2. Let α(k) = k 4 +2 √ k k 4 -2 √ k . Then for c d ≤ 1- 5cη 4

α(k)+1 , all patterns are detected with confidence c d .

This result shows that given a small training set size, and sufficiently large p + and p -, overparameterized networks converge to a global minimum which realizes the classifier f * with high probability and in a constant number of iterations. Furthermore, this global minimum detects all patterns in the data with confidence that increases with over-parameterization. The full proof of Theorem 5.2 is given in Sec. 8.6.

We will now sketch its proof. With probability at least (p + p -) m all training points are diverse and we will condition on this event. From Sec. 10 we can assume WLOG that the training set consists of one positive diverse point x + and one negative diverse point x -(since the network will have the same output on all same-label diverse points). We note that empirically over-parameterization improves generalization even when the training set contains non-diverse points (see Fig. 1 and Sec. 8.2). Now, to understand the dynamics of gradient descent it is crucial to understand the dynamics of the sets in Eq. 5. This follows since the gradient updates are expressed via these sets. Concretely, let

j ∈ W + t (i 1 ) ∩ W - t (i 2 )

then the gradient update is given as follows: 7

EQUATION

Similarly, for j ∈ U + t (i 1 ) ∩ U - t (i 2 ) the gradient update is given by:

EQUATION

Furthermore, the values of N W (x + ) and N W (x -) depend on these sets and their corresponding weight vectors, via sums of the form S + t , defined above. The proof consists of a careful analysis of the dynamics of the sets in Eq. 5 and their corresponding weight vectors. For example, one result of this analysis is that for all t ≥ 1 and i ∈ {1, 3} we have

W + t (i) = W + 0 (i) and the size of W + t (i) is at least k 2 -2 √ k with high probability.

There are two key technical observations that we apply in this analysis. First, with a small initialization and with high probability, for all 1 ≤ j ≤ k and 1 ≤ i ≤ 4 it holds that w

(j) 0 • x i ≤ η 4 and u (j) 0 • x i ≤ η

4 . This allows us to keep track of the dynamics of the sets in Eq. 5 more easily. For example, by this observation it follows that if for some j * ∈ W + t (2) it holds that j * ∈ W + t+1 (4), then for all j such that j ∈ W + t (2) it holds that j ∈ W + t+1 (4). Hence, we can reason about the dynamics of several filters all at once, instead of each one separately. Second, by concentration of measure we can estimate the sizes of the sets in Eq. 5 at iteration t = 0. Combining this with results of the kind W + t (i) = W + 0 (i) for all t, we can understand the dynamics of these sets throughout the optimization process.

The theorem consists of optimization and generalization guarantees. For the optimization guarantee we show that gradient descent converges to a global minimum. To show this, the idea is to characterize the dynamics of S + t using the characterization of the sets in Eq. 5 and their corresponding weight vectors. We show that as long as gradient descent did not converge to a global minimum, S + t cannot decrease in any iteration and it is upper bounded by a constant. Furthermore, we show that there cannot be too many consecutive iterations in which S + t does not increase. Therefore, after sufficiently many iterations gradient descent will converge to a global minimum.

We will now outline the proof of the generalization guarantee. Denote the network learned by gradient descent by N W T . First, we show that the network classifies all positive points correctly.

7 Note that with probability 1, σ (w

(j) t • xi 1 ) = 1, σ (w (j) t • xi 2 ) = 1

for all t, and therefore we omit these from the gradient update. This follows since σ (w

(j) t • xi 1 ) = 0 for some t only if w (j) 0 • xi 1 is an integer multiple of η.

Define the following sums for all 1 ≤ i ≤ 4:

X + t (i) = j∈W + T (i) max k σ w (j) • x + k , Y + t (i) = j∈U + T (i) max k σ u (j) • x + k (8)

First we notice that for all positive z we have

N W T (z) min{X + T (1), X + T (3)} -Y + T (2) -Y + T (4).

Then by the fact that N W T (x + ) ≥ γ at the global minimum, we can show that X + T (1) + X + T (3) is sufficiently large. As mentioned previously, by concentration of measure, W + 0 (i) is sufficiently large. Then by a symmetry argument we show that this implies that both X + T (1) and X + T (3) are sufficiently large. This shows that patterns x 1 and x 3 are detected. Finally, we show that

Y + T (2) + Y +

T (4) is not too large due to an upper bound on -N W T (x -). Hence, we can show that each positive point is classified correctly. The proof that all negative points are classified correctly and patterns x 2 and x 4 are detected is similar but slightly more technical. We refer the reader to Sec. 8.6 for further details.

5.2. SAMPLE COMPLEXITY LOWER BOUND FOR SMALL NETWORKS (k = 2):

The following theorem provides generalization lower bounds of global minima in the case that k = 2 and in a slightly more general setting than the one given in Theorem 5.2. Theorem 5.3. Let S = S + ∪ S -be a training set as in Sec. 3. Assume that gradient descent runs with parameters η

= cη k where c η ≤ 1 41 , σ g ≤ cη 16k 3 2

, k = 2 and γ ≥ 1. Then the following holds:

1. With probability at least (p + p -) m (1 -c) 33 48 , gradient descent converges to a global minimum that has non-zero test error. Furthermore, for c d ≥ 2c η , there exists at least one pattern which is not detected by the global minimum with confidence c d .

2. The non-zero test error above is at least p * .

The theorem shows that for a training set that is not too large and given sufficiently large p + and p -, with constant probability, gradient descent will converge to a global minimum that is not the classifier f * . Furthermore, this global minimum does not detect at least one pattern. The proof of the theorem is given in Sec. 8.7.

We will now provide a short outline of the proof. Let w

EQUATION

T and u

(2) T be the filters of the network at the iteration T in which gradient descent converges to a global minimum. The proof shows that gradient descent will not learn f * if one of the following conditions is met: a)

W + T (1) = ∅. b) W + T (3) = ∅. c) u (1) T • x 2 > 0 and u (2) T • x 2 > 0. d) u (1) T • x 4 > 0 and u (2) T • x 4 > 0.

Then by using a symmetry argument which is based on the symmetry of the initialization and the training data it can be shown that one of the above conditions is met with high constant probability. Finally, it can be shown that if one of these conditions hold, then at least one pattern is not detected.

6. EXPERIMENTS:

We perform several experiments that corroborate our theoretical findings. In Sec. 8.5 we empirically demonstrate our insights on the inductive bias of gradient descent. In Sec. 6.2 we evaluate a model compression scheme implied by our results, and demonstrate its success on the MNIST dataset.

6.1. PATTERN DETECTION:

In this section we perform experiments to examine the insights from our analysis on the inductive bias of gradient descent. Namely, that over-parameterized networks are biased towards global minima that detect more patterns in the data than global minima found by smaller networks. We check this both on the XORD problem which contains 4 possible patterns in the data and on an instance of an extension of the XORD problem, that we refer to as the Orthonormal Basis Detection (OBD) problem, which contains 60 patterns in the data. In Sec. 8.5 we provide details on the experimental setups.

Under review as a conference paper at ICLR 2019 Due to space considerations, we will not formally define the OBD problem in this section. We refer the reader to Sec. 8.5 for a formal definition. Informally, The OBD problem is a natural extension of the XORD problem that contains more possible patterns in the data and allows the dimension of the filters of the convolutional network to be larger. The patterns correspond to a set of orthonormal vectors and their negations. The ground truth classifier in this problem can be realized by a convolutional network with 4 channels.

In Fig. 2 we show experiments which confirm that in the OBD problem as well, overparameterization improves generalization. We further show the number of patterns detected in %0 training error solutions for different number of channels, in both the XORD and OBD problems. It can be clearly seen that for both problems, over-parameterized networks are biased towards %0 training error solutions that detect more patterns, as predicted by the theoretical results.

6.2. NETWORK COMPRESSION:

By inspecting the proof of Theorem 5.2, one can see that the dynamics of the filters of an overparameterized network are such that they either have low norm, or they have large norm and they point to the direction of one of the patterns (see, e.g., Lemma 8.4 and Lemma 8.6). This suggests that by clustering the filters of a trained over-parameterized network to a small number of clusters, one can create a significantly smaller network which contains all of the detectors that are needed for good generalization performance. Then, by training the last layer of the network, it can converge to a good solution. Following this insight, we tested this procedure on the MNIST data set and a 3 layer convolutional network with convolutional layer with multiple channels and 3 × 3 kernels, max pooling layer and fully connected layer. We trained an over-parameterized network with 120 channels, clustered its filters with k-means into 4 clusters and used the cluster centers as initialization for a small network with 4 channels. Then we trained only the fully connected layer of the small network. In Fig. 3 we show that for various training set sizes, the performance of the small network improves significantly with the new initialization and nearly matches the performance of the overparameterized network.

7. CONCLUSIONS:

In this paper we consider a simplified learning task on binary vectors and show that overparameterization can provably improve generalization performance of a 3-layer convolutional network trained with gradient descent. Our analysis reveals that in the XORD problem overparameterized networks are biased towards global minima which detect more relevant patterns in the data. While we prove this only for the XORD problem and under the assumption that the training set contains diverse points, our experiments clearly show that a similar phenomenon occurs in other settings as well. We show that this is the case for XORD with non-diverse points (Figure 1 ) and in the more general OBD problem which contains 60 patterns in the data and is not restricted to binary inputs (Figure 2 ). Furthermore, our experiments on MNIST hint that this is the case in MNIST as well (Figure 3 ).By clustering the detected patterns of the large network we could achieve better accuracy with a small network. This suggests that the larger network detects more patterns with gradient descent even though its effective size is close to that of a small network.

We believe that these insights and our detailed analysis can guide future work for showing similar results in more complex tasks and provide better understanding of this phenomenon. It would also be interesting to further study the implications of such results on model compression and on improving training algorithms. We tested the generalization performance in the setup of Section3. We considered networks with number of channels 4,6,8,20,50,100 and 200. The distribution in this setting has p + = 0.5 and p -= 0.9 and the training sets are of size 12 (6 positive, 6 negative). Note that in this case the training set contains non-diverse points with high probability. The ground truth network can be realized by a network with 4 channels. For each number of channels we trained a convolutional network 100 times and averaged the results. In each run we sampled a new training set and new initialization of the weights according to a gaussian distribution with mean 0 and standard deviation 0.00001. For each number of channels c, we ran gradient descent with learning rate 0.04 c and stopped it if it did not improve the cost for 20 consecutive iterations or if it reached 30000 iterations. The last iteration was taken for the calculations. We plot both average test error over all 100 runs and average test error only over the runs that ended at 0% train error. In this case, for each number of channels 4,6,8,20,50,100,200 the number of runs in which gradient descent converged to a 0% train error solution is 62, 79, 94, 100, 100, 100, 100, respectively.

8.3. HINGE LOSS CONFIDENCE:

Figure 5 shows that setting γ = 5 gives better performance than setting γ = 1 in the XORD problem.

The setting is similar to the setting of Section 8.2.1. Each point is an average test error of 100 runs.

8.4 EXPERIMENTS FOR SECTION 5.2

Theorem 5.3 holds for any η ≤ 1 82 and σ ≤ 1 1900 . Because the result is a lower bound, it is desirable to understand the behaviour of gradient descent for values outside these ranges. In Figure 6 we empirically show that for values outside these ranges, there is a generalization gap between gradient descent for k = 2 and gradient descent for larger k.

8.5. EXPERIMENTAL SETUP IN SECTION 6:

We will first formally define the OBD problem. Fix an even dimension parameter d 1 ≥ 2. In this problem, we assume there is an orthonormal basis B = {v 1 , ..., v d1 } of R d1 . Divide B into two equally sized sets B 1 and B 2 , each of size d1

2 . Now define the set of positive patterns to be

P = {v | v ∈ B 1 } ∪ {-v | v ∈ B 1 } and negative patterns to be N = {v | v ∈ B 2 } ∪ {-v | v ∈ B 2 }.

Let P OBD = P ∪ N . For d 2 > 0, we assume the input domain is X ⊆ R d1d2 and each x ∈ X is a vector such that x = (x 1 , ..., x d2 ) where each x i ∈ P OBD . We define the ground truth classifier f OBD : X → {±1} such that f OBD (x) = 1 if and only there exists at least one x i such that x i ∈ P . Notice that for d 1 = 2 and by normalizing the four vectors in {±1} 2 to have unit norm, we get the XORD problem. We note that the positive patterns in the XORD problem are defined to be P XOR and the negative patterns are {±1} 2 \ P XOR .

Let D be a distribution over X 2d × {±1} such that for all (x, y) ∼ D, y = f OBD (x). As in the XORD problem we define the distributions D + and D -. We consider the following learning task which is the same as the task for the XORD problem. We assume that we are given a training set S = S + ∪ S -⊆ {±1} d1d2 × {±1} where S + consists of m IID points drawn from D + and S -consists of m IID points drawn from D -. The goal is to train a neural network with randomly initialized gradient descent on S and obtain a network N : R d1d2 → R such that sign (N (x)) = f OBD (x) for all x ∈ {±1} d1d2 .

We consider the same network as in the XORD problem (Eq. 1), but now the filters of the convolution layer are d 1 -dimensional. Formally, for an input x = (x 1 , ..., x d ) ∈ X the output of the network is given by

N W (x) = k i=1 max σ w (i) • x 1 , ..., σ w (i) • x d -max σ u (i) • x 1 , ..., σ u (i) • x d (9)

where W ∈ R 2k×d1 is the weight matrix which contains in the first k rows the vectors w (i) ∈ R d1 , in the next k rows the vectors u (i) ∈ R d1 and σ(x) = max{0, x} is the ReLU activation applied element-wise. We performed experiments in the case that d 1 = 30, i.e., in which there are 60 possible patterns.

In Figure 2a , for each number of channels we trained a convolutional network given in Eq. 9 with gradient descent for 100 runs and averaged the results. The we sampled 25 positive points and 25 negative points in the following manner. For each positive point we sampled with probability 0.25 one of the numbers [4,6,8,10] twice with replacement. Denote these numbers by m 1 and m 2 . Then we sampled m 1 different positive patterns and m 2 different negative patterns. Then we filled a 60d 1dimensional vectors with all of these patterns. A similar procedure was used to sample a negative point. We considered networks with number of channels 4,6,8,20,100 and 200 and 500. Note that the ground truth network can be realized by a network with 4 channels. For each number of channels we trained a convolutional network 100 times and averaged the results. For each number of channels c, we ran gradient descent with learning rate 0.2 c and stopped it if it did not improve the cost for 20 consecutive iterations or if it had 0% training error for 200 consecutive iterations or if it reached 30000 iterations. The last iteration was taken for the calculations.

We plot both average test error over all 100 runs and average test error only over the runs that ended at 0% train error. For each number of channels 4,6,8,20,100,200,500 the number of runs in which gradient descent converged to a 0% train error solution is 96, 99, 100, 100, 100, 100, 100, respectively. For each 0% train error solution we recorded the number of patterns detected with c d = 0.0001 according to the Definition 5.1 (generalized to the OBD problem). In the XORD problem we recorded similarly the number of patterns detected in experiments which are identical to the experiments in Section 8.2.1, except that in this case p + = p -= 0.98.

8.6. PROOF OF THEOREM 5.2:

We will first need a few notations. Define x 1 = (1, 1), x 2 = (1, -1), x 3 = (-1, -1), x 4 = (-1, 1) and the following sets:

W + t (i) = j | arg max 1≤l≤4 w (j) t • x l = i , U + t (i) = j | arg max 1≤l≤4 u (j) t • x l = i W - t (i) = j | arg max l∈{2,4} w (j) t • x l = i , U - t (i) = j | arg max l∈{2,4} u (j) t • x l = i

We can use these definitions to express more easily the gradient updates. Concretely, let j ∈ W + t (i 1 ) ∩ W - t (i 2 ) then the gradient update is given as follows: 8

EQUATION

Similarly, for j ∈ U + t (i 1 ) ∩ U - t (i 2 ) the gradient update is given by:

EQUATION

We denote by x + a positive diverse point and x -a negative diverse point. Define the following sums for φ ∈ {+, -}:

S φ t = j∈W + t (1)∪W + t (3) max σ w (j) • x φ 1 , ..., σ w (j) • x φ d P φ t = j∈U + t (1)∪U + t (3) max σ u (j) • x φ 1 , ..., σ u (j) • x φ d R φ t = j∈W + t (2)∪W + t (4) max σ w (j) • x φ 1 , ..., σ w (j) • x φ d - j∈U + t (2)∪U + t (4) max σ u (i) • x φ 1 , ..., σ u (i) • x φ d Note that R + t = R - t since for z ∈ {x + , x -} there exists i 1 , i 2 such that z i1 = x 2 , z i2 = x 4

. By the conditions of the theorem, with probability at least (p + p -) m all the points in the training set are diverse. From now on we will condition on this event. Furthermore, without loss of generality, we can assume that the training set consists of one diverse point x + and one negative points x -. This follows since the network and its gradient have the same value for two different positive diverse points and two different negative points. Therefore, this holds for the loss function defined in Eq. 4 as well.

We will now proceed to prove the theorem. In Section 8.6.1 we prove results on the filters at initialization. In Section 8.6.2 we prove several auxiliary lemmas. In Section 8.6.3 we prove upper bounds on S - t , P + t and P - t for all iterations t. In Section 8.6.4 we characterize the dynamics of S + t and in Section 8.6.5 we prove an upper bound on it together with upper bounds on N Wt (x + ) and -N Wt (x -) for all iterations t.

We provide an optimization guarantee for gradient descent in Section 8.6.6. We prove generalization guarantees for the points in the positive class and negative class in Section 8.6.7 and Section 8.6.8, respectively. We complete the proof of the theorem in Section 8.6.9.

8 Note that with probability 1, σ (w

(j) t • xi 1 ) = 1, σ (w (j) t • xi 2 )

= 1 for all t, and therefore we omit these from the gradient update. This follows since σ (w (j) t • xi 1 ) = 0 for some t if and only if w (j) 0 • xi 1 is an integer multiple of η.

8.6.1. INITIALIZATION GUARANTEES:

Lemma 8.1. With probability at least 1 -4e -8 , it holds that

W + 0 (1) ∪ W + 0 (3) - k 2 ≤ 2 √ k and U + 0 (1) ∪ U + 0 (3) - k 2 ≤ 2 √ k Proof. Without loss of generality consider W + 0 (1) ∪ W + 0 (3) . Since P j ∈ W + 0 (1) ∪ W + 0 (3) = 1 2

, we get by Hoeffding's inequality

P W + 0 (1) ∪ W + 0 (3) - k 2 < 2 √ k ≤ 2e -2(2 2 k) k = 2e -8

The result now follows by the union bound.

Lemma 8.2. With probability ≥ 1 -

√ 2k √ πe 8k , for all 1 ≤ j ≤ k and 1 ≤ i ≤ 4 it holds that w (j) 0 • x i ≤ η 4 and u (j) 0 • x i ≤ η 4 .

Proof. Let Z be a random variable distributed as N (0, σ 2 ). Then by Proposition 2.1.2 in Vershynin (2017), we have

P [|Z| ≥ t] ≤ 2σ √ 2πt e -t 2 2σ 2

Therefore, for all 1 ≤ j ≤ k and 1 ≤ i ≤ 4, P w

(j) 0 • x i ≥ η 4 ≤ 1 √ 32πk e -8k

and P u

(j) 0 • x i ≥ η 4 ≤ 1 √ 32πk e -8k

The result follows by applying a union bound over all 2k weight vectors and the four points x i , 1 ≤ i ≤ 4.

From now on we assume that the highly probable event in Lemma 8.2 holds. Lemma 8.3. N Wt (x + ) < 1 and -N Wt (x -) < 1 for 0 ≤ t ≤ 2.

Proof. By Lemma 8.2 we have

N W0 (x + ) = k i=1 max σ w (i) 0 • x + 1 , ..., σ w (i) 0 • x + d -max σ u (i) 0 • x + 1 , ..., σ u (i) 0 • x + d ≤ ηk 4 < γ

and similarly -N W0 (x -) < 1. Therefore, by Eq. 10 and Eq. 11 we get:

1. For i ∈ {1, 3}, l ∈ {2, 4}, j ∈ W + 0 (i) ∩ W - 0 (l), it holds that w (j) 1 = w (j) 0 -ηx l + ηx i .

2. For i ∈ {2, 4} and j ∈ W + 0 (i), it holds that w

(j) 1 = w (j) 0 . 3. For i ∈ {1, 3}, l ∈ {2, 4}, j ∈ U + 0 (i) ∩ U - 0 (l), it holds that u (j) 1 = u (j) 0 -ηx i + ηx l .

4. For i ∈ {2, 4} and j ∈ U + 0 (i), it holds that u

(j) 2 = u (j) 0 .

Applying Lemma 8.2 again and using the fact that η ≤ 1 8k we have N W1 (x + ) < γ and -N W1 (x -) < 1. Therefore we get,

1. For i ∈ {1, 3}, l ∈ {2, 4}, j ∈ W + 0 (i) ∩ W - 0 (l), it holds that w (j) 2 = w (j) 0 + 2ηx i .

2. For i ∈ {2, 4} and j ∈ W + 0 (i), it holds that w

(j) 2 = w (j) 0 . 3. For i ∈ {1, 3}, l ∈ {2, 4}, j ∈ U + 0 (i) ∩ U - 0 (l), it holds that u (j) 2 = u (j) 0 -ηx i + ηx l .

4. For i ∈ {2, 4} and j ∈ U + 0 (i), it holds that u

(j) 2 = u (j) 0 .

As before, by Lemma 8.2 we have N W2 (x + ) < γ and -N W2 (x -) < 1.

8.6.2. AUXILIARY LEMMAS:

Lemma 8.4. For all t ≥ 1 we have

W + t (i) = W + 0 (i) for i ∈ {1, 3}.

Proof. We will first prove that W + 0 (i) ⊆ W + t (i) for all t ≥ 1. To prove this, we will show by induction on t ≥ 1, that for all j ∈ W + 0 (i) ∩ W + 0 (l), where l ∈ {2, 4} the following holds:

1. j ∈ W + t (i). 2. w (j) t • x l = w (j) 0 • x l -η or w (j) t • x l = w (0) t • x l . 3. w (j) t • x i > η.

The claim holds for t = 1 by the proof of Lemma 8.3. Assume it holds for t = T . By the induction hypothesis there exists an l ∈ {2, 4} such that j ∈ W + T (i) ∩ W - T (l ). By Eq. 10 we have, w

T +1 = w (j)

EQUATION

)

where a ∈ {0, 1} and b ∈ {-1, 0}.

If w:

(j)

T •x l = w (j) 0 •x l then l = l and either w (j) T +1 •x l = w (j) 0 •x l if b = 0 or w (j) T +1 •x l = w (j) 0 •x l -η if b = -1. Otherwise, assume that w (j) T •x l = w (j) 0 •x l -η. By Lemma 8.2 we have 0 < w (j) 0 •x l < η 4 . Therefore -η < w (j) T • x l < 0 and l = l. It follows that either w (j) T +1 • x l = w (j) 0 • x l -η if b = 0 or w (j) T +1 • x l = w (j) 0 • x l if b = -1.

In both cases, we have w (j) T +1 • x l < η. Furthermore, by Eq. 12, w (j)

T +1 •x i ≥ w (j) T •x i > η. Hence, arg max 1≤l≤4 w (j) T +1 •x l = i which by definition implies that j ∈ W + T +1 (i).

This concludes the proof by induction which shows that

W + 0 (i) ⊆ W + t (i) for all t ≥ 1.

In order to prove the lemma, it suffices to show that

W + 0 (2) ∪ W + 0 (4) ⊆ W + t (2) ∪ W + t (4). This follows since 4 i=1 W + t (i) = {1, 2, .

.., k}. We will show by induction on t ≥ 1, that for all j ∈ W + 0 (2) ∪ W + 0 (4), the following holds:

1. j ∈ W + t (2) ∩ W + t (4). 2. w (j) t = w (j) 0 + mx 2 for m ∈ Z.

The claim holds for t = 1 by the proof of Lemma 8.3. Assume it holds for t = T . By the induction hypothesis j ∈ W + T (2) ∩ W + T (4). Assume without loss of generality that j ∈ W + T (2). This implies that j ∈ W - T (2) as well. Therefore, by Eq. 10 we have w (j)

T +1 = w (j) T + aηx 2 + bηx 2 (13)

where a ∈ {0, 1} and b ∈ {0, -1}. By the induction hypothesis, w (j)

T +1 = w (j) 0 + mx 2 for m ∈ Z. If a = 1 or b = 0 we have for i ∈ {1, 3}, w (j) T +1 • x 2 ≥ w (j) T • x 2 > w (j) T • x i = w (j) T +1 • x i

where the first inequality follows since j ∈ W + T (2) and the second by Eq. 13. This implies that j ∈ W + T +1 (2) ∩ W + T +1 (4).

Otherwise, assume that a = 0 and b = -1. By Lemma 8.2 we have w

(j) 0 • x 2 < η 4 . Since j ∈ W + T (2)

, it follows by the induction hypothesis that w

(j) T = w (j) 0 + mx 2

, where m ∈ Z and m ≥ 0. To see this, note that if m < 0, then w

(j) T • x 2 < 0 and j / ∈ W + T (2), which is a contradiction. Let i ∈ {1, 3}. If m = 0, then w (j) T +1 = w (j) 0 -x 2 , w (j) T +1 • x 4 > η 2 and w (j) T +1 • x i = w (j) 0 • x i < η 4 by Lemma 8.2. Therefore, j ∈ W + T +1 (4).

Otherwise, if m > 0, then w (j)

T +1 • x 2 ≥ w (j) 0 • x 2 > w (j) 0 • x i = w (j) T +1 • x i . Hence, j ∈ W + T +1

(2), which concludes the proof.

Lemma 8.5. For all t ≥ 0 we have

U + 0 (2) ∪ U + 0 (4) ⊆ U + t (2) ∪ U + t (4).

Proof. Let j ∈ U + 0 (2) ∪ U + 0 (4). It suffices to prove that u

(j) t = u (j) 0 + α t ηx 2 for α t ∈ Z. This follows since the inequalities u (j) 0 • x 1 < u (j) 0 • x 2 ≤ η 4 imply that in this case j ∈ U + t (2) ∪ U + t (4).

Assume by contradiction that there exist an iteration t for which u

(j) t = u (j) 0 + α t ηx 2 + β t ηx i where β t ∈ {-1, 1}, α t ∈ Z, i ∈ {1, 3} and u (j) t-1 = u (j) 0 + α t-1 ηx 2 where α t-1 ∈ Z. 9 Since the coefficient of x i changed in iteration t, we have j ∈ U + t-1 (1) ∪ U + t-1 (3).

However, this contradicts the claim above which shows that if u

(j) t-1 = u (j) 0 + α t-1 ηx 2 , then j ∈ U + t-1 (2) ∪ U + t-1 (4).

Lemma 8.6. Let i ∈ {1, 3} and l ∈ {2, 4}. For all t ≥ 0, if j ∈ U + 0 (i) ∩ U - 0 (l), then there exists

a t ∈ {0, -1}, b t ∈ N such that u (j) t = u (j) 0 + a t ηx i + b t ηx l .

Proof. First note that by Eq. 11 we generally have u

(j) t = u (j) 0 + αηx i + βηx l where α, β ∈ Z. Since u (j) 0 • x 1 ≤ η 4

, by the gradient update in Eq. 11 it holds that a t ∈ {0, -1}. Indeed, a 0 = 0 and by the gradient update if a t-1 = 0 or a t-1 = -1 then a t ∈ {-1, 0}.

Assume by contradiction that there exists an iteration t > 0 such that b t = -1 and b t-1 = 0. Note that by Eq. 11 this can only occur if j ∈ U + t-1 (l). We have u

(j) t-1 = u (j) 0 + a t-1 ηx i where a t-1 ∈ {0, -1}. Observe that u (j) t-1 • x i ≥ u (j) 0 • x i by the fact that u (j) 0 • x i ≤ η 4 . Since u (j) 0 • x i > u (j) 0 • x l = u (j) t-1 • x l we have j ∈ U + t-1 (1) ∪ U + t-1 (3), a contradiction.

Lemma 8.7. Let

X + t = j∈W + t (1) max σ w (i) • x + 1 , ..., σ w (i) • x + d and Y + t = j∈W + t (3) max σ w (i) • x + 1 , ..., σ w (i) • x + d

Then for all t,

X + t -X + 0 |W + t (1)| = Y + t -Y + 0 |W + t (3)| .

Proof. We will prove the claim by induction on t. For t = 0 this clearly holds. Assume it holds for t = T . Let j 1 ∈ W + T (1) and j 2 ∈ W + T (3). By Eq. 10, the gradient updates of the corresponding weight vector are given as follows:

EQUATION

EQUATION

T +1 • x + d = max σ w (j2) T • x + 1 , ..., σ w (j2) T • x + d + aη

By Lemma 8.4 we have

W + t (1) = W + 0 (1) and W + t (3) = W + 0 (3) for all t. It follows that X + T +1 -X + 0 W + T +1 (1) = aη W + 0 (1) + X + T -X + 0 W + 0 (1) = aη + Y + T -Y + 0 W + 0 (3) = aη W + 0 (3) + Y + T -Y + 0 W + 0 (3) = Y + T +1 -Y + 0 W + T +1

(3) where the second equality follows by the induction hypothesis. This proves the claim. 8.6.3 BOUNDING P + t , P - t AND S - t Lemma 8.8. The following holds

1. S - t ≤ W + t (1) ∪ W + t (3) η for all t ≥ 1. 2. P + t ≤ U + t (1) ∪ U + t (3) η for all t ≥ 1. 3. P - t ≤ U + t (1) ∪ U + t (3) η for all t ≥ 1.

Proof. In Lemma 8.4 we showed that for all t ≥ 0 and j ∈ W + t (1) ∪ W + t (3) it holds that w (j) t • x 2 ≤ η . This proves the first claim. The second claim follows similarly. Without loss of generality, let j ∈ U + t (1). By Lemma 8.5 it holds that U + t (1) ⊆ U + 0 (1) ∪ U + 0 (3) for all t ≤ t. Therefore, by Lemma 8.6 we have u (j) t x 1 < η, from which the claim follows.

For the third claim, without loss of generality, assume by contradiction that for j ∈ U + t (1) it holds that u

(j) t • x 2 > η. Since u (j) t • x 1 < η by Lemma 8.6, it follows that j ∈ U + t (2) ∪ U + t (4), a contradiction. Therefore, u (j) t • x 2 ≤ η for all j ∈ U + t (1) ∪ U + t (3)

, from which the claim follows.

8.6.4 DYNAMICS OF S + t Lemma 8.9. The following holds:

1. If N Wt (x + ) < γ and -N Wt (x -) < 1, then S + t+1 = S + t + η W + t (1) ∪ W + t (3) . 2. If N Wt (x + ) ≥ γ and -N Wt (x -) < 1, then S + t+1 = S + t . 3. If N Wt (x + ) < γ and -N Wt (x -) ≥ 1, then S + t+1 = S + t + η W + t (1) ∪ W + t (3) .

Proof.

1. The equality follows since for each i ∈ {1, 3}, l ∈ {2, 4} and j ∈ W + t (i) ∩ W - t (l) we have w

(j) t+1 = w (j) t + ηx i -ηx l and W + t+1 (1) ∪ W + t+1 (3) = W + t (1) ∪ W + t (3) by Lemma 8.4.

2. In this case for each i ∈ {1, 3}, l ∈ {2, 4} and j ∈ W + t (i) ∩ W - t (l) we have w

(j) t+1 = w (j) t -ηx l and W + t+1 (1) ∪ W + t+1 (3) = W + t (1) ∪ W + t (3) by Lemma 8.4.

3. This equality follows since for each i ∈ {1, 3}, l ∈ {2, 4} and j

EQUATION

4) (since x l will remain the maximal direction). Therefore,

EQUATION

In the second case, where we have 4) . By all these observations, we have

EQUATION

EQUATION

By Eq. 14 and Eq. 15, it follows that,

Z + t+1 + P + t+1 ≥ Z + t+1 ≥ Z + t + P + t + η U + t (2) ∪ U + t (4) . By induction we have Z + t+b + P + t+b ≥ Z + t + P + t + b-1 i=0 η U + t+i (2) ∪ U + t+i (4) . By Lemma 8.6 for any 1 ≤ i ≤ b -1 we have U + t+i (2) ∪ U + t+i (4) = {1, ..., k}. Therefore, Z + t+b + P + t+b ≥ Z + t + P + t + (b -1)c η .

Now, assume that j ∈ W + T (l) for l ∈ {2, 4}. Then w (j)

T +1 = w (j)

T -ηx l . Thus either max σ w (j)

T +1 • x + 1 , ..., σ w (j) T +1 • x + d -max σ w (j) T • x + 1 , ..., σ w (j) T • x + d = -η in the case that j ∈ W + T +1 (l), or max σ w (j) T +1 • x + 1 , ..., σ w (j) T +1 • x + d ≤ η if j / ∈ W + T +1 (l). Applying these observations b times, we see that Y + T +b -Y + T is at most η W + T +b (2) ∪ W + T +b (4) = η W + 0 (2) ∪ W + 0 (4)

where the equality follows by Lemma 8.4. By Lemma 8.9, we have S + T +b = S +

T . Hence, we can conclude that

N W T +b (x + ) -N W T (x + ) = S + T +b + R + T +b -P + T +b -S - T -R + T + P + T = Y + T +b -Z + T +b -P + T +b -Y + T + Z + T + P + T ≤ -(b -1)c η + η W + 0 (2) ∪ W + 0 (4) Lemma 8.11. Assume that N Wt (x + ) < γ and -N Wt (x -) ≥ 1 for T ≤ t < T + b where b ≥ 1. Then -N W T +b (x -) ≤ -N W T (x -) -bη W + 0 (2) ∪ W + 0 (4) + c η .

Proof. Define

Y - t = j∈W + t (2)∪W + t (4) max σ w (i) • x + 1 , ..., σ w (i) • x + d and Z - t = k j=1 max σ u (j) • x + 1 , ..., σ u (j) • x + d

First note that by Lemma 8.4 we have

W + t+1 (2) ∪ W + t+1 (4) = W + t (2) ∪ W + t (4).

Next, for any l ∈ {2, 4} and j ∈ W + t (l) we have w

(j) t+1 = w (j) t + ηx l . Therefore, Y - T +b ≥ Y - T + bη W + T (2) ∪ W + T (4) = Y - T + bη W + 0 (2) ∪ W + 0 (4)

where the second equality follows by Lemma 8.4. Assume that j ∈ U + T (l) for l ∈ {1, 3}. Then u (j)

T +1 = u (j)

T -ηx l and max σ u (j)

T +1 • x - 1 , ..., σ u (j) T +1 • x - d -max σ u (j) T • x - 1 , ..., σ u (j) T • x - d = 0

(16) To see this, note that by Lemma 8.6 and Lemma 8.5 it holds that u

(j) T = u (j) 0 + a T ηx l where a T ∈ {-1, 0}. Hence, u (j) T +1 = u (j) 0 + a T +1 ηx l where a T +1 ∈ {-1, 0}. Since u (j) 0 • x 2 < η 4 it follows that u (j) T +1 • x 2 = u (j) T • x 2 = u (j) 0 •

x 2 and thus Eq. 16 holds. Now assume that j ∈ U + T (l) for l ∈ {2, 4}. Then

max σ u (j) T +1 • x - 1 , ..., σ u (j) T +1 • x - d -max σ u (j) T • x - 1 , ..., σ u (j) T • x - d = -η if l ∈ {2, 4} and j ∈ U + T +1 (l), or max σ u (j) T +1 • x - 1 , ..., σ u (j) T +1 • x - d ≤ η

if l ∈ {2, 4} and j / ∈ U + T +1 (l). Applying these observations b times, we see that Z - T +b -Z - T is at most η U + T +b (2) ∪ U + T +b (4) . Furthermore, for j ∈ W + T (l), l ∈ {1, 3}, it holds that w (j)

T +1 = w (j)

T + ηx l . Therefore max σ w (j)

T +1 • x - 1 , ..., σ w (j) T +1 • x - d = max σ w (j) T • x - 1 , ..., σ w (j) T • x - d and since W + T +1 (1) ∪ W + T +1 (3) = W + T (1) ∪ W + T (3) by Lemma 8.4, we get S - T +b = S - T . Hence, we can conclude that -N W T +b (x -) + N W T (x -) = -S - T +b -Y - T +b + Z - T +b + S - T + Y - T -Z - T ≤ -bη W + 0 (2) ∪ W + 0 (4) + η U + T +b (2) ∪ U + T +b (4) ≤ -bη W + 0 (2) ∪ W + 0 (4) + c η

Lemma 8.12. For all t, N Wt (x

+ ) ≤ γ + 3c η , -N Wt (x -) ≤ 1 + 3c η and S + t ≤ γ + 1 + 8c η .

Proof. The claim holds for t = 0. Consider an iteration T . If

N W T (x + ) < γ then N W T +1 (x + ) ≤ N W T (x + )+2ηk ≤ γ +2c η . Now assume that N Wt (x + ) ≥ γ for T ≤ t ≤ T +b and N W T -1 (x + ) < γ. By Lemma 8.10, it holds that N W T +b (x + ) ≤ N W T (x + ) + ηk ≤ N W T (x + ) + c η ≤ γ + 3c η ,

where the last inequality follows from the previous observation. Hence, N Wt (x + ) ≤ γ + 3c η for all t.

The proof of the second claim follows similarly. It holds that Proof. First note that with probability at least 1 -√ 2k √ πe 8k -4e -8 the claims of Lemma 8.1 and Lemma 8.2 hold. Now, if gradient descent has not reached a global minimum at iteration t then either N Wt (x + ) < γ or -N Wt (x -) < 1. If -N Wt (x + ) < γ then by Lemma 8.9 it holds that

-N W T +1 (x -) < 1 + 2c η if -N W T (x -) < 1. Otherwise if -N Wt (x -) ≥ 1 for T ≤ t ≤ T + b and -N W T -1 (x -) < 1 then -N W T +b (x -) ≤ 1 +

S + t+1 ≥ S + t + η W + 0 (1) ∪ W + 0 (3) ≥ S + t + k 2 -2 √ k η (17)

where the last inequality follows by Lemma 8.1.

If N Wt (x + ) ≥ γ and -N Wt (x -) < 1 we have S + t+1 = S + t by Lemma 8.9. However, by Lemma 8.10, it follows that after 5 consecutive iterations t < t < t + 6 in which N W t (x + ) ≥ γ and -N W t (x -) < 1, we have N Wt+6 (x + ) < γ. To see this, first note that for all t, N Wt (x + ) ≤ γ+3c η by Lemma 8.12. Then, by Lemma 8.10 we have

N Wt+6 (x + ) ≤ N Wt (x + ) -5c η + η W + 0 (2) ∪ W + 0 (4) ≤ γ + 3c η -5c η + c η < γ

where the second inequality follows by Lemma 8.1 and the last inequality by the assumption on k.

Assume by contradiction that GD has not converged to a global minimum after T = 7(γ+1+8cη)

( k 2 -2 √ k)η

iterations. Then, by the above observations, and the fact that S + 0 > 0 with probability 1, we have

S + T ≥ S + 0 + k 2 -2 √ k η T 7 > γ + 1 + 8c η

However, this contradicts Lemma 8.12.

8.6.7. GENERALIZATION ON POSITIVE CLASS:

We will first need the following three lemmas. Lemma 8.14. With probability at least 1 -4e -8 , it holds that

W + 0 (1) - k 4 ≤ 2 √ k and W + 0 (3) - k 4 ≤ 2 √ k

Proof. The proof is similar to the proof of Lemma 8.1.

Lemma 8.15. Assume that gradient descent converged to a global minimum at iteration T . Then there exists an iteration T 2 < T for which S + t ≥ γ + 1 -3c η for all t ≥ T 2 and for all t < T 2 , -N Wt (x -) < 1.

Proof. Assume that for all 0 ≤ t ≤ T 1 it holds that N Wt (x + ) < γ and -N Wt (x -) < 1. By continuing the calculation of Lemma 8.3 we have the following:

1. For i ∈ {1, 3}, l ∈ {2, 4}, j ∈ W + 0 (i) ∩ W - 0 (l), it holds that w (j)

T1 = w (j) 0 + T 1 ηx i - 1 2 (1 -(-1) T1 )ηx l .

2. For i ∈ {2, 4} and j ∈ W + 0 (i), it holds that w (j)

T1 = w (j) 0 . 3. For i ∈ {1, 3}, l ∈ {2, 4}, j ∈ U + 0 (i) ∩ U - 0 (l), it holds that u (j) T1 = u (j) 0 -ηx i + ηx l .

4. For i ∈ {2, 4} and j ∈ U + 0 (i), it holds that u (j)

T1 = u (j) 0 .

Therefore, there exists an iteration T 1 such that

N W T 1 (x + ) ≥ γ and -N W T 1 (x -) < 1 and for all t < T 1 , N Wt (x + ) < γ and -N Wt (x -) < 1. Let T 2 ≤ T be the first iteration such that -N W T 2 (x -) ≥ 1. We claim that for all T 1 ≤ t ≤ T 2 we have N W T 1 (x + ) ≥ γ -2c η . It suffices to

show that for all T 1 ≤ t < T 2 the following holds:

1. If N Wt (x + ) ≥ γ then N Wt+1 (x + ) ≥ γ -2c η . 2. If N Wt (x + ) < γ then N Wt+1 (x + ) ≥ N Wt (x + ).

The first claim follows since at any iteration N Wt (x + ) can decrease by at most 2ηk = 2c η . For the second claim, let t < t be the latest iteration such that N W t (x + ) ≥ γ. Then at iteration t it holds that -N W t (x -) < 1 and N W t (x + ) ≥ γ. Therefore, for all i ∈ {1, 3}, l ∈ {2, 4} and

j ∈ U + 0 (i) ∩ U + 0 (l) it holds that u (j) t +1 = u (j)

t + ηx l . Hence, by Lemma 8.5 and Lemma 8.6 it holds that U + t +1 (1) ∪ U + t +1 (3) = ∅. Therefore, by the gradient update in Eq. 11, for all 1 ≤ j ≤ k, and all t < t ≤ t we have u

(j) t +1 = u (j) t , which implies that N W t +1 (x + ) ≥ N W t (x + ). For t = t we get N Wt+1 (x + ) ≥ N Wt (x + ). The above argument shows that N W T 2 (x + ) ≥ γ -2c η and -N W T 2 (x -) ≥ 1. Since N W T 2 (x + ) - N W T 2 (x -) = S +

T2 -P + T2 +P - T2 -S - T2 , P - T2 , S - T2 ≥ 0 and P - T2 ≤ c η it follows that S + T2 ≥ γ+1-3c η . Finally, by Lemma 8.9 we have S + t ≥ γ + 1 -3c η for all t ≥ T 2 . Lemma 8.16. Let

X + t = j∈W + t (2)∪W + t (4) max σ w (j) • x + 1 , ..., σ w (j) • x + d and Y + t = j∈U + t (2)∪U + t (4) max σ u (j) • x + 1 , ..., σ u (j) • x + d

Assume that k ≥ 64 and gradient descent converged to a global minimum at iteration T . Then,

X + T ≤ 34c η and Y + T ≤ 1 + 38c η .

Proof. Notice that by the gradient update in Eq. 10 and Lemma 8.2, X + t can be strictly larger than max X 4) . By Lemma 8.9, S + t increases in this case by η W + t (1) ∪ W + t (3) . We know by Lemma 8.15 that there exists T 2 < T such that S + T2 ≥ γ+1-3c η and that N Wt (x + ) < γ and -N Wt (x -) ≥ 1 only for t > T 2 . Since S + t ≤ γ + 1 + 8c η for all t by Lemma 8.12, there can only be at most

EQUATION

11cη η|W + T (1)∪W + T (3)| iterations in which N Wt (x + ) < γ and -N Wt (x -) ≥ 1. It follows that X + t ≤ η W + T (2) ∪ W + T (4) + 11c η η W + T (2) ∪ W + T (4) η W + T (1) ∪ W + T (3) ≤ c η + 11c η k 2 + 2 √ k k 2 -2 √ k ≤ 34c η

where the second inequality follows by Lemma 8.1 and the third inequality by the assumption on k.

At convergence we have

N W T (x -) = S - T + X + T -Y + T -P - T ≥ -1 -3c η by Lemma 8.12 (recall that R - t = R + t = X + t -Y + t )

. Furthermore, P - T ≥ 0 and by Lemma 8.8 we have S - T ≤ c η . Therefore, we get Y + T ≤ 1 + 38c η .

We are now ready to prove the main result of this section.

Proposition 8.17. Define β(γ) = Assume without loss of generality that z i = (-1, -1) = x 3 . Define

EQUATION

Furthermore, by Lemma 8.7 we have

EQUATION

and by Lemma 8.14,

k 4 -2 √ k k 4 + 2 √ k ≤ W + T (1) W + T (3) ≤ k 4 + 2 √ k k 4 -2 √ k (20) Let α(k) = k 4 +2 √ k k 4 -2 √ k . By Lemma 8.2 we have X + 0 (1) ≤ ηk 4 ≤ cη 4 .

Combining this fact with Eq. 19 and Eq. 20 we get

EQUATION

which implies together with Eq. 18 that

X + T (3) ≥ γ+1- 5cη 4 1+α(k) . Therefore, N W T (z) ≥ X + T (3) -P + T -Y + T (2) -Y + T (4) ≥ γ + 1 - 5cη 4 1 + α(k) -c η -1 -3(8c η ) -14c η = γ + 1 - 5cη 4 1 + α(k) -39c η -1 > 0 (21)

where the first inequality is true because

EQUATION

The second inequality in Eq. 21 follows since P + T ≤ c η and by appyling Lemma 8.16. Finally, the last inequality in Eq. 21 follows by the assumption on k. 10 Hence, z is classified correctly.

8.6.8. GENERALIZATION ON NEGATIVE CLASS:

We will need the following lemmas. Lemma 8.18. With probability at least 1 -8e -8 , it holds that We note that by the analysis in Lemma 8.18, it holds that for any t, j 1 ∈ U + 0 (2) and j 2 ∈ U + 0 (4), either j 1 ∈ U + t (2) and j 2 ∈ U + t (4), or j 1 ∈ U + t (4) and j 2 ∈ U + t (2). We assume without loss of generality that j 1 ∈ U + T (2) and j 2 ∈ U + T (4). It follows that in this case N W T (z) ≤ S - T + X - T -Z - T (2) -Y - T (2). 12 Otherwise we would replace Y - T (2) with Y - T (4) and vice versa and continue with the same proof. 

EQUATION

Y - T (4) ≤ α(k)Y - T (2) + Y ≤ α(k)Y - T (2) + c η

Plugging these inequalities in Eq. 24 we get:

α(k)Z - T (2) + c η 4 + α(k)Y - T (2) + c η + Y - T (2) + Z - T (2) ≥ 1 which implies that Y - T (2) + Z - T (2) ≥ 1 - 5cη 4 α(k) + 1

By Lemma 8.16 we have X - T ≤ 34c η . Hence, by using the inequality S - T ≤ c η we conclude that

N W T (z) ≤ S - T + X - T -Z - T (2) -Y - T (2) ≤ 35c η - 1 - 5cη 4 α(k) + 1 < 0

where the last inequality holds for k > 64 β+1

β-1

2:

. 13 Therefore, z is classified correctly.

8.6.9 FINISHING THE PROOF First, for k ≥ 120, with probability at least 1 -√ 2k √ πe 8k -16e -8 , Proposition 8.13, Lemma 8.14 and Lemma 8.18 hold. Also, for the bound on T , note that in this case and let β = max{β 1 , β 2 }. For γ ≥ 8 and c η ≤ 1 410 it holds that 64 β+1 β-1 2 < 120. By Proposition 8.17 and Proposition 8.21, it follows that for k ≥ 120 gradient descent converges to a global minimum which classifies all points correctly.

We will now prove pattern detection results. In the case of over-paramterized networks, in Proposition 8.17 we proved that X + (1), X + (3) ≥ 1. We refer to Eq. 17 in the proof of Proposition 8.13. To show convergence and provide convergence rates of gradient descent, the proof uses Lemma 8.1. However, to only show 12 The fact that we can omit the term -Z - T (4) from the latter inequality follows from Lemma 8.6. 

≥ k 2 -2 √ k lη -kη ≥ 1

where the last ineqaulity follows by the assumption on l. Proof. Proposition 9.4 implies that there are at most 4k k-2 √ k + 40 iterations in which there exists (x i , y i ) such that -y i N Wt (x i ) < 1. After at most that many iterations, gradient descent converges to a global minimum.

10. VC DIMENSION:

As noted in Remark 3.1, the VC dimension of the model we consider is at most 15. To see this, we first define for any z ∈ {±1} 2d the set P z ⊆ {±1} 2 which contains all the distinct two dimensional binary patterns that z has. For example, for a positive diverse point z it holds that P z = {±1} 2 . Now, for any points z (1) , z (2) ∈ {±1} 2d such that P z (1) = P z (2) and for any filter w ∈ R 2 it holds that max j σ w • z

(1) j = max j σ w • z

(2) j . Therefore, for any W , N W (z (1) ) = N W (z (2) ).

Specifically, this implies that if both z (1) and z (2) are diverse then N W (z (1) ) = N W (z (2) ). Since there are 15 non-empty subsets of {±1} 2 , it follows that for any k the network can shatter a set of at most 15 points, or equivalently, its VC dimension is at most 15. Despite these expressive power limitations, there is a generalization gap between small and large networks in this setting, as can be seen in Figure 1 .

:

See Definition 5.1 for a formal definition of detection of a pattern.

For simplicity, we consider this setting of equal number of positive and negative points in the training set.

In practice it is common to set γ to 1. In our analyis we will need γ ≥ 8 to guarantee generalization. In Section 8.3 we show empirically, that for this task, setting γ to be larger than 1 results in better test performance than setting γ = 1.

Note thatHoffer et al. (2018) show that fixing the last layer weights to ±1 does not degrade performance in various tasks. This assumption also appeared in other works(Brutzkus et al., 2018;Li & Yuan, 2017).

We note that this generalization gap holds for global minima (0 train error). Therefore, the theorem can be read as follows. For k ≥ 120, given 2 samples, with probability at least 1 -δ, gradient descent converges to a global minimum with at most test error. On the other hand, for k = 2 and given number of samples less than 2 log 48δ 33(1-c) log(p + p -) , with probability greater than δ, gradient descent converges to a global minimum with error greater than . See Section 5 for further details.

Note that in each iteration βt changes by at most η.

Note that this holds after conditioning on the corresponding event of Lemma 8.2.

Figures and Tables:

Figure 1: Over-parameterization improves generalization in the XORD problem. The network in Eq. 1 and Fig. 4 is trained on data from the XORD problem (see Sec. 3). The figure shows the test error obtained for different number of channels k. The blue curve shows test error when restricting to cases where training error was zero. It can be seen that increasing the number of channels improves the generalization performance. Experimental details are provided in Section 8.2.1.

Figure 2: Inductive bias in XORD and OBD problems. (a) Over-parameterization improves generalization in the OBD problem (b) Pattern detection phenomenon in the XORD problem (c) Pattern detection phenomenon in the OBD problem. In both (b) and (c) we see that as the number of channels increase, gradient descent is biased towards %0 training error solutions with more detected patterns.

Figure 3: Model compression in MNIST. The plot shows the test error of the small network (4 channels) with standard training (red), the small network that uses clusters from the large network (blue), and the large network (120 channels) with standard training (green). It can be seen that the large network is effectively compressed without losing much accuracy.

Figure 4: Network architecture used for training in the XORD problem.

Figure 5: Higher confidence of hinge-loss results in better performance in the XORD problem.

3c η by Lemma 8.11.The third claim holds by the following identities and boundsN W T (x + ) -N W T (x -) = S + T -P + T + P - T -S - T , P - T ≥ 0, P + T ≤ c η , S - T ≤ c η and N W T (x + ) -N W T (x -) ≤ γ + 1 + 6cη by the previous claims.8.6.6 OPTIMIZATIONWe are now ready to prove a global optimality guarantee for gradient descent. Proposition 8.13. Let k > 16 and γ ≥ 1. With probabaility at least 1iterations, gradient descent converges to a global minimum.

8k -8e -8 , gradient descent converges to a global minimum which classifies all positive points correctly.Proof. With probability at least 1 -Proposition 8.13, and Lemma 8.14 hold. It suffices to show generalization on positive points. Assume that gradient descent converged to a global minimum at iteration T . Let (z, 1) be a positive point. Then there exists z i ∈ {(1, 1), (-1, -1)}.

) -39cη -1 > 0 is equivalent to α(k) < β(γ) which is equivalent to k > 64 β(γ)+1 β(γ)-1 2 .

8.19 and Lemma 8.18 there exists Y ≤ c η such that:

. Since for i ∈ {1, 3} it holds that D xi ≥ X + (i), it follows that patterns x 1 and x 3 are detected. Similarly, in Proposition 8.21 our analysis implies that, without loss of generality, Y - l ∈ {2, 4}, D x l ≥ Y - T (l) + Z - T (l) (under the assumption that we assumed without loss of generality), it follows that patterns x 2 and x 4 are detected. The confidence of the detection is at least

Assume that k ≥ 25. With probability ≥ 1 -√ 2k √ πe 8k -8e -8 , after at most 4k k-2 √ k + 40 iterations, gradient descent converges to a global minimum.

13 It holds that 35cη -Proof.1. For t = 0 the claim holds by Lemma 8.2. Assume by contradiction that there exists t > 0, such that R + t (1) + R - t (1) > kη. It follows that, without loss of generality, there exists j ∈ U + t (1) such that σ u • x 1 > η. In each iteration u • x 1 can increase by at most η, therefore by Lemma 8.2 there exists 0 ≤ t < t such that 0 < σ u +1 • x 1 > η. However, in this case u + αx 1 + βx 2 + γx 4 where α ≤ 0. Therefore, u • x 1 ≤ η, a contradiction. 2. This is a direct consequence of Lemma 9.1.3. By Lemma9.1, if j ∈ W + t (1) and -yN Wt (x 1 ) < 1 then w + η 4 x 1 +βx 2 +γx 4 , from which the first part of the claim follows. The second claim follows similarly. Proposition 9.4. Assume that k ≥ 25. With probability ≥ 1πe 8k -8e -8 , for all i, if until iteration T there were at least l ≥ k k-2 √ k + 10 iterations, in which -yN Wt (x i ) < 1, then it holds that -yN Wt (x i ) ≥ 1 for all t ≥ T . Proof. Without loss of generality assume that i = 1. By Lemma 9.3 and Lemma 8.2, with probability ≥ 1πe 8k -8e -8 , if -yN Wt (x 1 ) < 1 then S + t+1 (1) ≥ S + t (1) + k 2 -2 √ k η. Therefore, by Lemma 9.3, for all t ≥ T N Wt (x) = S +

Table content: <table><tr><td/><td/><td>(j)</td><td>(j)</td></tr><tr><td/><td/><td>(j) t • x 1 ≤ η</td></tr><tr><td colspan="2">and σ u</td><td>(j) t (j) t +1 = u (j)</td></tr><tr><td/><td/><td>(j) t +1 • x 1 &lt; u</td><td>(j)</td></tr><tr><td/><td/><td>(j) t+1 = w</td><td>(j)</td></tr><tr><td/><td/><td>√ √</td><td>2k</td></tr><tr><td>√ √</td><td>2k</td></tr><tr><td/><td/><td>1-</td><td>5cη 4</td></tr></table>

Peer review (iclr2019):
 The paper studies a particular task (the XOR detection problem) in a particular setup (see below), and proves mathematically that in that case, the training performs better when the number of features grows. The task is the following one: - consider a set of pairs of binary values (-1 or +1); - detect whether at least one of these pairs is (+1, +1) or (-1, -1). The design of the predictor is: - for each pair, compute 2k features (of the form ReLu(linear combination of the values, without bias)); - compute the max over all pairs of these features (thus obtaining 2k values); - return the k first values minus the k last ones. The training set consists only of examples having the following property [named *diversity*]: - if the example (which is a set of pairs) is negative (i.e. doesn*t contain (+1,+1) nor (-1,-1)), then it contains both (-1,1) and (1,-1); - if the example is positive, it contains all possible pairs. The paper proves that, under this setup, training with a number of features k > 120 will perform better than with k = 2 only (while k = 2 is theoretically sufficient to solve the problem). While tackling an interesting problem (impact of over-parameterization), the proof is specific to this particular, unusual architecture, with a "max - max" over features independently computed for each pair that the example contains; it relies heavily on the fact that the input are binary, and that the number of possible input pairs is small (4), which implies that the features can take only 4 values. Note also that the probabilities in some theorems are not really probabilities of convergence/performance of the training algorithm per se (as one would expect in such PAC-looking bounds), but actually probabilities of the batch of examples to all satisfy some property (the diversity). Thus it is difficult to get from this study any insight about the over-parameterization / training ability phenomenon, for more general tasks, datasets or architectures. Though clearly an impressive amount of work has been done in this proof, I do not see how it can be generalized (there is no explanation in the paper in that regard either, while it would have been welcomed), and consequently be of interest for the vast majority of the ICLR community, which is why I call for rejection.