This work provides an additional step in the theoretical understanding of neural networks. We consider neural networks with one hidden layer and show that when learning symmetric functions, one can choose initial conditions so that standard SGD training efficiently produces generalization guarantees. We empirically verify this and show that this does not hold when the initial conditions are chosen at random. The proof of convergence investigates the interaction between the two layers of the network. Our results highlight the importance of using symmetry in the design of neural networks. Building a theory that can help to understand neural networks and guide their construction is one of the current challenges of machine learning. Here we wish to shed some light on the role symmetry plays in the construction of neural networks. It is well-known that symmetry can be used to enhance the performance of neural networks. For example, convolutional neural networks (CNNs) (see Lecun et al. (1998) ) use the translational symmetry of images to classify images better than fully connected neural networks. Our focus is on the role of symmetry in the initialization stage. We show that symmetry-based initialization can be the difference between failure and success. On a high-level, the study of neural networks can be partitioned to three different aspects. Expressiveness Given an architecture, what are the functions it can approximate well? Training Given a network with a "proper" architecture, can the network fit the training data and in a reasonable time? Generalization Given that the training seemed successful, will the true error be small as well? We study these aspects for the first "non trivial" case of neural networks, networks with one hidden layer. We are mostly interested in the initialization phase. If we take a network with the appropriate architecture, we can always initialize it to the desired function. A standard method (that induces a non trivial learning problem) is using random weights to initialize the network. A different reasonable choice is to require the initialization to be useful for an entire class of functions. We follow the latter option. Our focus is on the role of symmetry. We consider the following class of symmetric functions S = S n = n ∑ i=0 a i · 1 |x|=i : a 1 , . . . , a n ∈ {±1} , where x ∈ {0, 1} n and |x| = ∑ i x i . The functions in this class are invariant under arbitrary permutations of the input's coordinates. The parity function π(x) = (−1) |x| and the majority function are well-known examples of symmetric functions. Expressiveness for this class was explored by Minsky and Papert (1988) . They showed that the parity function cannot be represented using a network with limited "connectivity". Contrastingly, if we use a fully connected network with one hidden layer and a common activation function (like sign, sigmoid, or ReLU) only O(n) neurons are needed. We provide such explicit representations for all functions in S; see Lemmas 1 and 2. We also provide useful information on both the training phase and generalization capabilities of the neural network. We show that, with proper initialization, the training process (using standard SGD) efficiently converges to zero empirical error, and that consequently the network has small true error as well. Theorem 1. There exists a constant c > 1 so that the following holds. There exists a network with one hidden layer, cn neurons with sigmoid or ReLU activations, and an initialization such that for all distributions D over X = {0, 1} n and all functions f ∈ S with sample size m ≥ c(n+log(1/δ ))/ε, after performing poly(n) SGD updates with a fixed step size h = 1/poly(n) it holds that is the network after training over S. The number of parameters in the network described in Theorem 1 is Ω(n 2 ). So in general one could expect overfitting when the sample size is as small as O(n). Nevertheless, the theorem provides generalization guarantees, even for such a small sample size. The initialization phase plays an important role in proving Theorem 1. To emphasize this, we report an empirical phenomenon (this is "folklore"). We show that a network cannot learn parity from a random initialization (see Section 5.3). On one hand, if the network size is big, we can bring the empirical error to zero (as suggested in Soudry and Carmon (2016) ), but the true error is close to 1/2. On the other hand, if its size is too small, the network is not even able to achieve small empirical error (see Figure 5 ). We observe a similar phenomenon also for a random symmetric function. An open question remains: why is it true that a sample of size polynomial in n does not suffice to learn parity (with random initialization)? A similar phenomenon was theoretically explained by Shamir (2016) and Song et al. (2017) . The parity function belongs to the class of all parities where · is the standard inner product. This class is efficiently PAC-learnable with O(n) samples using Gaussian elimination. A continuous version of P was studied by Shamir (2016) and Song et al. (2017) . To study the training phase, they used a generalized notion of statistical queries (SQ); see Kearns (1998) . In this framework, they show that most functions in the class P cannot be efficiently learned (roughly stated, learning the class requires an exponential amount of resources). This framework, however, does not seem to capture actual training of neural networks using SGD. For example, it is not clear if one SGD update corresponds to a single query in this model. In addition, typically one receives a dataset and performs the training by going over it many times, whereas the query model estimates the gradient using a fresh batch of samples in each iteration. The query model also assumes the noise to be adversarial, an assumption that does not necessarily hold in reality. Finally, the SQ-based lower bound holds for every initialization (in particular, for the initialization we use here), so it does not capture the efficient training process Theorem 1 describes. Theorem 1 shows, however, that with symmetry-based initialization, parity can be efficiently learned. So, in a nutshell, parity can not be learned as part of P, but it can be learned as part of S. One could wonder why the hardness proof for P cannot be applied for S as both classes consist of many input sensitive functions. The answer lies in the fact that P has a far bigger statistical dimension than S (all functions in P are orthogonal to each other, unlike S). The proof of the theorem utilizes the different behavior of the two layers in the network. SGD is performed using a step size h that is polynomially small in n. The analysis shows that in a polynomial number of steps that is independent of the choice of h the following two properties hold: (i) the output neuron reaches a "good" state and (ii) the hidden layer does not change in a "meaningful" way. These two properties hold when h is small enough. In Section 5.2, we experiment with large values of h. We see that, although the training error is zero, the true error becomes large. Here is a high level description of the proof. The neurons in the hidden layer define an "embedding" of the inputs space X = {0, 1} n into R (a.k.a. the feature map). This embedding changes in time according to the training examples and process. The proof shows that if at any point in time this embedding has good enough margin, then training with standard SGD quickly converges. This is explained in more detail in Section 3. It remains an interesting open problem to understand this phenomenon in greater generality, using a cleaner and more abstract language. This work demonstrates that symmetries can play a critical role when designing a neural network. We proved that any symmetric function can be learned by a shallow neural network, with proper initialization. We demonstrated by simulations that this neural network is stable under corruption of data, and that the small step size is the proof is necessary. We also demonstrated that the parity function or a random symmetric function cannot be learned with random initialization. How to explain this empirical phenomenon is still an open question. The works Shamir (2016) and Song et al. (2017) treated parities using the language of SQ. This language obscures the inner mechanism of the network training, so a more concrete explanation is currently missing. We proved in a special case that the standard SGD training of a network efficiently produces low true error. The general problem that remains is proving similar results for general neural networks. A suggestion for future works is to try to identify favorable geometric states of the network that guarantee fast convergence and generalization. Proof. For all k ∈ A and x ∈ X of weight k, the first inequality holds since ∆ i (x) ≥ 0 for all i and x. For all k ∈ A and x ∈ X of weight k, = 2 exp(−2.5)/(1 − exp(−5)) < 0.17; the first equality follows from the definition, the second equality follows from σ (5(x + 0.5)) − σ (5(x − 0.5)) = σ (5(x + 0.5)) + σ (5(−x + 0.5)) − 1 for all x, the first inequality neglects the negative sums, and the second inequality follows because exp(ξ ) > σ (ξ ) for all ξ .
When initialized properly, neural networks can learn the simple class of symmetric functions; when initialized randomly, they fail.  
{"src": "scitldr-AIC_train", "paper_id": "Skeh-xBYDH"}