On Symmetry and Initialization for Neural Networks
Authors: Ido Nachum
Amir Yehudayoff
Venue:  (2020)
Keywords: Neural Network Theory
Symmetry

Abstract: 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.

Under review as a conference paper at ICLR 2020
ON SYMMETRY AND INITIALIZATION FOR NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
This work provides an additional step in the theoretical understanding 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 ver- ify 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.
INTRODUCTION
Building a theory that can help to understand neural networks and guide their construction one of the current challenges of machine learning. Here wish shed some light on the role sym- metry 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-basee initialization can be the difference between failure and success.
On a high-level, the study of neural networks can be partitioned 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 mostly interested in the initialization phase. we take network with the appropriate architecture, we can always initialize it to the desired function. A standard method (that induces non trivial learning problem) is using random weights initialize the network. A different reason- able 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=
Σ a. 1.. :1,=:,,,...444 {+1) 1=0
where x E (0, 1 and E The functions in this class are invariant under arbitrary permu-
tations of the input's coordinates. The parity function π(x) (-1)1+) and the majority function well-known examples of symmetric functions.
Expressiveness for this class was explored by Minsky and Papert 1988) parity function cannot be represented using a network with limited "connectivity". Contrastingly, if we a fully connected network with one hidden layer and common activation function (like sign, sigmoid, or ReLU) only Onn) neurons are needed. We provide such explicit representations for all functions in S; see Lemmas T and
They showed that the

---

Under review as a conference paper at ICLR 2020
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 <> 1 so that the following holds. There exists a network with one hidden layer, en neurons with sigmoid or ReLU activations, and an initialization such that for all distributions 2 over X = {0,1}" and all functions ʃ T& with sample size m 2 c(n+log( (og(1/8)) after performing poly(n) SGD updates with a fixed step size = 1/ poly(n) it holds that
(is: Pr (Ns(x) * f(x)) > ((m))=})) <8
P
where S = ((xx (Nm, (Xm)) and (s(x) is the network after training over S.
The number of parameters in the network described in Theorem is (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 | 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 similar phenomenon also for a random symmetrie function. An open question remains: why is it true that sample of size polynomial in и 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
P= P, = (-1)"=ss=>
=
where is the standard inner product. This class efficiently PAC-leamable with O()) samples using Gaussian climination. A continuous version of P was studied by Shamir (0016) and Song al. (017).. To study the training phase, they used generalized notion of statistical queries (SQ); see Kearns [1998). In this framework, they show that most functions in the class IP 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 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, 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 I describes.
assumption that does not necessarily
Theorem [ shows, however, that with symmetry-based initialization, parity can be efficiently learned. So, in nutshell, parity can not be learned part of IP, but it can be learned as part of S. One could wonder why the hardness proof for IP cannot be applied for S as both classes con- sist of many input sensitive functions. The answer lies in the fact that P has a far bigger statistical dimension than S (all functions in IP 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 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 high level description of the proof. The neurons in the hidden layer define an "embed- ding" of the inputs space X = 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 cleaner and more abstract language.
=00, {0,1)" into R (a.k.a. the feature map). This embedding changes in
2

---

Under review as a conference paper at ICLR 2020
1.1 BACKGROUND
To better understand the context of our research, we survey previous related works.
The expressiveness and limitations of neural networks were studied in several works such Rahimi and Recht (2008): | Telgarsky (0166: Fldan and Shamir (2016) and Arora et al. (2016). Constructions
of small ReLU networks for the parity function appeared several previous works, such Wilam- lowsk et al. 2003), Arslanov et al. (2016), Arslanov et al. (2002) and Masato Iyoda et al. (003)).
Constant depth circuits for the parity function were also studied in the context of computational
complexity theory, see for example Furst et al. (9881, Ajtai (983) and Hástad (9877).
The training phase of neural networks was also studied in many works. Here we list several works that seem most related to ours. [aaniely (2017) analyzed SGD for general neural network architecture and showed that the training error can be nullified, e.g., for the class of bounded degree polynomials (see also Andoni et al. (2014)). Jacot et al. (2018) studied neural tangent kernels (NTK), an infinite width analogue of neural networks. [u et al. (2018) showed that randomly initialized shallow ReLU networks nullify the training error, long the number of samples is smaller than the number of neurons in the hidden layer. Their analysis only deals with optimization over the first layer (so that the weights of the output neuron are fixed). Chizat and Bach (2018) provided another analysis of the latter two works. Allen-ZZhu et al.] (2018b) showed that over- aver-parametrized neural networks can achieve zero training error, as long the data points not too close to another and the weights of the output neuron are fixed. /Zou et (2018)) provided guarantees for zero training error, assuming the two classes are separated by a positive margin.
Convergence and generalization guarantees for neural networks were studied in the following works. Brutzkus et al. (2017) studied linearly separable data. Li and Liang (2018) studied well separated distributions. Allen-Zhu et al. (2018a) gave generalization guarantees in expectation for SGD. SGD.,Arora Arora (2019) gave data detendependent generalization bounds for GD. All these works optimized only over the hidden layer (the output layer is fixed after initialization).
Margins play an important role learning, and we also use it in our proof. (ookolic et al. (2016). Sokolic et al. (2017). Bartlett et al.] (2017) and [Sun et al. (2015) gave generalization bounds for neural networks that are based on their margin when the training ends. From a practical perspective, Elsayed et al. (2018), Romero and Alquezar (2002) Lid et al. (016)) suggested different training
algorithms that optimize the margin.
As discussed above, it seems difficult for neural networks to learn parities. [ong et al. (2017) and [Shamir (2066) demonstrated this using the language statistical queries (SQ). This is a valuable language, but it misses some central aspects of training neural networks. SQ seems to be closely related to GD, but does not seem to capture SGD. SQ also shows that many of the parities functions &iesX; difficult learn, but it does not imply that the parity function (n) is difficult to learn. Abbe and Sandon (2018) demonstrated a similar phenomenon in setting that is closer to the "real life" mechanics of neural networks.
We suggest that taking the symmetries of the learning problem into account can make the difference between failure and success. Several works suggested different neural architectures that take sym- metries into account; see Zaheer et al. (2017), Gens and Domingos (2014), and Cohen and Welling (2016).
REPRESENTATIONS
Here we describe efficient representations for symmetric functions by networks with one hidden layer. These representations are also useful later on, when we study the training process. We study two different activation functions, sigmoid and ReLU (similar statement can be proved for other activations, like arctan). Each activation function requires its own representation, as in the two lemmas below.
2.1 SIGMOID
We start with the activation a(E) = [)) since it helps to understand the construction for the ReLU activation. The building blocks of the symmetric functions indicators of [x] for
3

---

Under review as a conference paper at ICLR 2020
0.
03
02
PUELI AETHARRR
Figure I: Approximations of the symmetric function fa = sign Ctea - 0.5) by sigmoid and
ReLU activations for A = 21,,
i iE (0, In. An indicator function is essentially the difference between two sigmoid functions:
sign( -ign(1 - = sign(A;- - -0.5),
where 4:(x) = ((((())) ((4((()) -i
- ii-0.))
Lemma 1. The symmetric function SA sign(Eie^ |//=i - 0.5) satisfies fa(x) sign(-0.5 + Lies (x))), where A C [n].
A network with one hidden layer of n n neurons with sigmoid activations and one bias neuron is sufficient to represent any function in S. The coefficients of the sigmoid gates are 0, in this representation. The proofs of this lemma and the subsequent lemmas appear in the appendix.
2.2 RELU
sigmoid function can be represented using ReLU(E)) max (0,5) as the difference between two ReLUs
a (5 ReLU 1) Re)U((x
Hence, indicator function can be represented using sign | 0.5) sign(T, 0.5) where
(x) ReLU i+ - 2 - + ReLU((x -i 1).
Lemma 2. The symmetric function sign (EAA ||/- 0.5) satisfies fa(x sign(-0.5 +
Eics EicA [xx)), where A c [n].
The lemma shows that network with one hidden layer of n 3 ReLU neurons and one bias neuron sufficient represent any function S. The coefficients of the ReLU gates 1, this representation.
3 TRAINING AND GENERALIZATION
The goal of this section is to describe a small network with one hidden layer that (when initialized properly) efficiently learns symmetric functions using a small number of examples (the training is done via SGD).
3.1
SPECIFICATIONS
Here we specify the architecture, initialization and loss function that is implicit in our main result (Theorem l).
To guarantee convergence of SGD, we need to start with "good" initial conditions. The initialization pick depends the activation function uses, and is chosen with resemblance Lemma for
4

---

Under review as a conference paper at ICLR 2020
ReLU. On high level, this indicates that understanding the class of functions wish to study in term of "representation" can be helpful when choosing the architecture neural network in learning context.
The network we consider has one hidden layer. We denote by Wij the weight between coordinate j of the input and neuron i in the hidden layer. We denote W this matrix of weights. We denote by b the bias neuron i the hidden layer. We denote this vector of weights. We denote by mi is the weight from neuron in the hidden layer to the output neuron. We denote M this vector of weights. We denote by b the bias of the output neuron.
Initialize the network follows: The dimensions of W are (n (n++)) 3) x For all 1 sis (n+ and b, -i+ 2. We set M = 0 and b = O.
S j S we set Wij = and
To run SGD, we need choose a loss function. We use the hinge loss,
[xx. = (x)x(xxxxxx M + b) B}}
where V ReLU is the output of the hidden layer input x and B > 0 parameter of confidence.
3.2 MARGINS
A key property in the analysis is the 'margin' of the hidden layer with respect to the function being leameed
A map V + {=1} over finite set V Fd is linearly separable if there exists Rd such that sign(w v) = (vv) for all v e V. When the Euclidean norm of w is ||w|| 1, the num- ber marg(w, () m ( the margin of with respect to Y. The number marg(Y) = suPweRd:]ww]]= marg(w; w. Y) is the margin of Y.
We are interested in the following set V in TRd. Recall that W is the weight matrix between the input layer and the hidden layer, and that B is the relevant bias vector. Given W. B. we are interested in the set = (', x E X}. where V, = ReLU(Wx+ B). words, we think of the neurons in the hidden layer defining "embedding" of X in Euclidean space. A similar construction works for other activation functions. We say that Y
{+1} agrees with f E S if for all x E X it holds that
Y (vx)= = f(x).
The following lemma bounds from below the margin of the initial V.
Lemma 3. Y partition that agrees with some function in for the initialization described above then marg(Y) 2 (n)/vn).
Proof. By Lemmas D and we see that any function in can be represented with vector of weights M, E [-1, 1, (n)) the output neuron together with a bias These M,b induce a partition
Y V. Namely, Y (v, M vy + b 0.25 for all.x E X. Since (Ml O( (() we have our desired result.
3.3 FREEZING THE HIDDEN LAYER
Before analyzing the full behavior of SGD,, make observation: if the weights of the hidden layer are fixed with the initialization described above, then Theorem[[ Tholds for SGD with batch size This observation, unfortunately, does not suffice prove Theorem [ In the setting we consider, the training of the neural network uses SGD without fixing any weights. This more general case is handled in the next section. The rest of this subsection is devoted for explaining this observation.
Novikoff (1922) showed that that the perceptron algorithm Rosenblatt (1958) makes a small num- ber of mistakes for linearly separable data with large margin. For a comprehensive survey of the perceptron algorithm and its variants, see Moran et al. (018).
Running SGD with the hinge loss induces the same update nule as in a modified perceptron algo- rithm, Algorithm[] [
A standard "lifting" that adds coordinate with to every vector allows to translate the affine case to the
linear

---

Under review as a conference paper at ICLR 2020
Algorithm The modified perceptron algorithm
Initialize: w0)) = 0, = 0, B > and > 0
while 3v E V with ((v) v S B do
w((++)== = + (r)vhh
-= end while return wi())
Novikoff's proof can be generalized to any B > O and batches of any size to yield the following theorem; see Collobert and Bengio (2004); Krauth and Mezard (1987) and appendix A
Theorem 2. For Y - } with margin Y and step size O, the modified perceptron
algorithm performs af most 20b-(RA))
updates and achieves margin of at least
188h where
(yh)-
(ph+
R = max.ev ||v|]
So, when the weights of the hidden layer are fixed, Lemma implies that the number of SGD steps is at most polynomial in n.
3.4 STABILITY
When SGD the entire network, the layers interact. For ReLU network time the update rule for W is as follows. If the network classifies the input x correctly with confidence more than B. change is made. Otherwise, we change the weights in M by AM = -vyh, where y the true label and h is the step size. If also neuron of the hidden fired on we update its incoming weights by AW1:- = ympth. These update rules define the following dynamical system: (a)
w(++1) (()) + ((MT))
w(++1) w +y (M!!)) T
1o 1yylx+BB/ h
(2)
B((+1) -B +y (M()) T
OO (wox+ xB)++B1)))
(3)
M(++1) M + ReLU (w BBI
(4)
b(++)) +yh,
(5)
where is the Hcaviside step function and is the Hadamard pointwise product.
A key observation in the proof is that the weights of the last layer (4 and (5)) are updated exactly as the modified perceptron algorithm. Another key statement in the proof is that if the network has reached good representation of the input (i.c., the hidden layer has a large margin), then the interaction between the layers during the continued training does not impair this representation. This summarized in the following lemma (we not aware of similar statement in the literature).
Lemma 4. Let M O, b O, and (ReLU : EX} be linearly separable embedding of X and with margin 7 > O by the hidden layer of neurul network of depth two with ReLU activation and weights given by W.B. Let Rx = max ||x|], let R = maxyev ||v||- and 0 < h S
100R-Ry the integration step. Assuming Rx >> and y SSS 1, and using f = R2h the loss function,
1022
after t SGD iterations the following hold:
Each v moves a distance at at most 12
The norm [MO]] is at most O(Rhv/t).
The training ends at most ORR² /T2) SGD updates.
Intuitively, this type of lemma can be useful in many other contexts. The high level idea is to identify "good geometric structure" that the network reaches and enables efficient learning.

---

Under review as a conference paper at ICLR 2020
4
MAIN RESULT
Proof of Theorem
7 There is an unknown distribution 9 over the space X. We pick i.idd. examples (#+log(1/8)) according 2, where y; fx;) for some ES. Run SGD for (n*)) steps, where the step size is (1)/n²) and the parameter of the loss function B R²h with R n!/2.
S= ((x,,y1)),-.. Ym)) where cl
We claim that it suffices to show that at the end of the training (i) the network correctly classifies all the sample points xI...., Amm. and (ii) for every x E such that there exists S i m with |x] = [xi] the network outputs y; on well. Here is why. The initialization of the network embeds the space X into n + 4 dimensional space (including the bias neuron of the hidden layer). Let v()) be the initial embedding (0)
x X}. Although X = 2", the size of y(o) is + 1. The VC dimension of all the boolean functions over ( is + 1. Now, samples suffice to yield true error for an ERM when the VC dimension is n + I; see e.g. Theorem 6.7 in SShaee-Shwarte and 4). It remains prove (i) and (ii) above.
X+
Ben-David (014))
the beginning of the training, the partition of v0 defined by the target f S has a margin of y = (R) We are interested in the eventual V = (ReLL x -*) : X} embedding of X well. The modified perceptron algorithm together with aemmaaguaramme after K < 20R² /12 = ((n)) updates, (M", bb) separates the embedded sample V3 [RRLU(W"*x + B²): : m) with margin of at least 0.9y/3.
By Lemma
that
It remains to prove (ii). Lemma 4 states that as long less than K = O(n") updates were made, the elements in V moved at most 0(1 011/n²). At the end of the training, the embedded sample Vs is separated with a margin of at least 0.9y/3 with respect to the hyperplane defined by M" and B*. Each Vi for E X moved at most (1/n")) < 7/4. This means that if [x] = |ay then the network has the same output on and x, Since the network has zero empirical error, the output on this x is as well.
A similar proof is available with sigmoid activation (with better convergence rate and larger allowed step size).
Remark. The generalization part of the above proof can be viewed as consequence of sample compression (Littlestone and Warmuth (1986)). Although the eventual network depends on all ex- amples, the proof shows that its functionality depends on most n examples. Indeed, after the training, all examples with equal hamming weight have the same label.
Remark. The parameter B = R2h h we chose in the proof may seem odd and negligible. It a construct in the proof that allows us bound esficiently the distance that the elements in V have moved during the training. For all practical purposes B = O works as well (see Figure[4
5 EXPERIMENTS
We accompany the theoretical results with some experiments. We used network with one hidden layer of 4n +3 neurons, ReLU activation, and the hinge loss with n/',. In all the experiments, we used SGD with mini-batch of size one and before each epoch we randomized the sample. We ob- served similar behavior for larger mini-batches, other activation functions, and other loss functions. The graphs that appear in the appendix present the training error and the true erro versus the epoch of the training process. In all the comparisons below, we chose a random symmetric function and random sample from X.
5.1 THE THEORY IN PRACTICE
Figure demonstrates our theoretical results and also validates the performance of our initialization. In one setting, we trained only the second layer (freezed the weights of the hidden layer) which
We deal with high dimensional spaces, the true error not calculated exactly but approximated on an independent batch of samples of size 104.
7

---

Under review as a conference paper at ICLR 2020
essentially corresponds to the perceptron algorithm. In the second setting, trained both layers with step size n1 (as the theory suggests). As expected, performance in both cases is similar. We remark that SGD continues to run even after minimizing the empirical error. This happens because of the parameter B
5.2 OVERSTEPPING THE THEORY
Here we experiment with two parameters in the proof, the step size h and the confidence parameter B. In Figure 3 we used three different step sizes, two of which much larger than the theory suggests. We see that the training error converges much faster to zero, when the step size is larger. This fast convergence comes at the expense of the true error. For a large step size, generalization cease to hold.
Setting = h a construct in the proof. Figure 4 shows that setting B does not impair the performance. The difference between theory (requires >> 0) and practice (allows B = 0) can be explained as follows. The proof bounds the worst-case movement of the hidden layer, whereas in practice average-case argument suffices.
5.3 HARD TO LEARN PARITY
Figure shows that even for 20, learning parity is hard from a random initialization. When the sample size is small the training eπror can be nullified but the true error is large. As the sample grows, becomes much harder for the network to nullify even the training error. With our initializa- tion, both the training error and true error are minimized quickly. Figure demonstrates the same phenomenon for a random symmetric function.
5.4 CORRUPTION OF DATA
Our initialization also delivers satisfying results when the input data it corrupted. In figure 7 we randomly perturb (with probability = 1 the labels and use the same SGD to train the model. In figure randomly shift every entry of the vectors in the space X by that is uniformly distributed 0.
CONCLUSION
This work demonstrates that symmetries play critical role when designing 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 still an open question. The works works(Shamir (2016) and (Sng 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.
REFERENCES
Emmanuel Abbe and Colin Sandon. Provable limitations of deep learning, 2018.
M. Ajtai. formmull on finite structures. Annals of Pure and Applied Logic, 24(1), pages 1-48, 1983.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond layers. CoRR, 0bs/1881..4991 2018a.
8

---

Under review as a conference paper at ICLR 2020
Zeyuan Allen-Zhu, Yuanzhi Li. and Zhao Song. parameterization. CoRR, abs//&11.000 81.00966,, 2018b.
convergence theory for deep learning via
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning polynomials with neural networks. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference Machine Learning, volume of Proceedings of Machine Leurning Rexearch, pages 1908-1916, 2014.
Raman Arora, Amitabh Basu, Poorya Mianjy. and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. CoRR, abs/161 611..... 1.00191,, 2016.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. CoRR, abs/1901 08584, 2019.
Marat Arslanov, Zhazira E. Amirgalicva, and Chingiz A. Kenshimov. N-bit parity neural networks with mini- mum number of threshold neurons. Open Engineering, 6, 01 2016.
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally normalized margin bounds for neural networks, 2017.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over-parameterized networks that provably generalize on linearly separable data. In ICLR, 2018.
Lenaic Chizat and Francis Bach. note on lazy training in supervised diffcrentiable programming, 12, 2018.
Taco S. Cohen and Max Welling. Group equivariant convolutional networks, 2016.
Ronan Collobert and Samy Bengio. Links between perceptrons, mips and svms. In Proceedings of the Twenty- first International Conference on Machine Learning, ICML '04, page 23, 2004.
Amit Daniely. Sgd learns the conjugate kernel class of the network. Advances Neural Information Processing Systems 30, pages 2422-2430, 2017.
Simon Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. CoRR, abs/ 181.0000,,, 2018.
Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks. In JMLR 49, pages 1-34. 2016.
Gamaleldin F. Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. In NIPS, pages 850-860, 2018.
Merrick Furst, James B. Saxe. and Michael Sipser. Parity, circuits, and the polynomial-time time hierarchy. In FOCS. pages 260-270, 1981.
Robert Gens and Pedro M Domingos. Deep symmetry networks. In Advances in Neural Information Processing Systems 27, pages 2537-2545, 2014.
Johan Håstad. Computational Limitations of Small-depth Circuits. MIT Press, Cambridge, MA, USA, 1987,
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NIPS, pages 8580-8589, 2018.
Michael Kearns, Efficient noise-tolerant learning from statistical queries. J. ACM, 45 (6), pages 983-1006. 1998.
Werner Krauth and Mare Mezard. Learning algorithms with optimal stability in neural networks. J. Phys., A20, pages L745-L752, 1987.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-basse learning applied to document recognition. Proceedings of the IEEE, 86 (11), pages 2278-2324, 1998.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data, 2018
Nick Littlestone and Manfred K. Warmuth. Relating data compression and Icarability. Technical report, 1986.
Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Meng Yang. Large-margin softmax loss for convolutional neural networks. In JCML, 2016.
Eduardo Masato Tyoda, Hajime Nobuhara, and Kaoru Hirota. A solution for the n-bit parity problem using single translated multiplicative neuron. Neural Processing Letters, 18:233-238, 12 2003.

---

Under review as a conference paper at ICLR 2020
Marvin L. Minsky and Seymour A. Papert. Perceptrons: Expunded Edition. MIT Press, Cambridge, MA. USA, 1988.
Shay Moran, Ido Nachum, Itai Panasoff, and Amir Ychudayoff. On the perceptron's compression. CoRR, abs/1806.05400 2018.
Albert B.J. Novikoff. On convergence proofs pereeptrons. In Proceedings of the Symposium the Mathe- matical Theory of Automata, volume 12, pages 615 622, 1962.
Ali Rahimi and Benjamin Recht. Random features for lcrge-scale kernel machines. In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 1177- 1184, 2008.
E. Romero and Alquezar. Maximizing the margin with feedforward neural networks. In Proceedings 2002 International Joint Conference on Neural Networks, IJCNN'02 (Cat. No.02CH37290), volume pages 743-748, 2002.
Rosenblatt. The perceptron: probabilistic model for information storage organization in the brain. Psychological Review, pages 65 386, 1958.
Shai Shalev-Shwarde and Shai bridge university press, 2014.
Understanding machine learning: From theory to algorithms. Cam-
Ohad Shamir. Distribution speliffcc hardness of learning neural networks. CoRR, abs/1609.01000 609.00037 2016.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Margin preservation of deep neural networks. CoRR, has/1605.08254 2016.
Jure Sokolie, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65, pages 4265 4280, 2017.
Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. CoRR, abs/1707.046155, 2017.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training enror guarantees for multi- layer neural networks. 2016.
Shizhao Sun, Wei Chen, Liwei Wang, and Tie-Yan Liu. Large margin deep neural networks: Theory and algorithms. CoRR, abs/15506.0222,, 2015.
Matus Telgarsky. Representation Benefits of Deep Feedforward Networks. In JMLR, 49, pages 23,,, 2016.
Bogdan Wilamowski, David Hunter, and Aleksander Malinowski, Solving parity-n problems with feodforward neural networks. In IJCNN, pages 2546 - 2551, 08 2003.
M Arslamov, D U. Ashigaliev, and Esraa Ismail. N-bit parity ordered neural networks. Neurocomputing. 48: 1053-1056, 10 2002.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- parameterized deep relu networks. CoRR, abs/1811.08883 2018.
A
APPENDIX
PROOF OF LEMMA
Proof. For all & A x X of weight
Σ
(K) > (x
a 0.5) - o(-5-0.5) > 0.84;
AEA
10

---

Under review as a conference paper at ICLR 2020
the first inequality holds since (xx) for all i and For all & and e of weight k,
Σ
(x)
Σ 0 (0-
IEA
IEA
Σ ((5
Σ
005 (i+ -k)
k<tEA
isied
Σ
1o (55.((+) - +|
Σ
[0 (k--(k-i+055)) -
k<iFA
Σ (5-((k11+0.5)
Σ
(1+
ESTEd
Σ eepp(5 (-i+0.5))
2exp( (00xp(-2.3)/111111 (xpp3) 0.17:
the first equality follows from the definition. the second equality follows from ( 0.5)) o5(x 0.5))
(5(x 0.5)) (5(xx++ for all x, the first inequality neglects the negative sums, and the second inequality follows because exp(5) (5)) for all
PROOF OF LEMMA
Proof. The proof follows from two observations:
For all the support of [,(x) ReLU((x] - 2R) RRLU(()) -i 1) ------L-------ss-ss-------------
for all x weight not A holds ΣeA [)(x) 0.
x weight holds (x(x =
PROOF OF LEMMA
Proof. We are interested in maximal distance embedding of an element E has moved from initial
emhedding:
00)
[ReLU(W( BB)) ReLU( B
(6)
|w]) - w(0) Rx + |B8 - B
[w(R) - wit wik-i)/ 1/| [(()) B - 1)
Rx
(8)
To simplify equations 2
discussed above, assume that during the optimization process the norm of the weights and grow a maximal rate:
( w = 1 ((MO)) No (woxx BBO)) JT s (ar0))
Rxh,
[+0+1) B80 (m Ho (w B()) n s |
(10)
here the of matrix is the f2-norm.
To bound these quantities, we follow the modified perceptron proof and add another quantity to bound. That is, the maximal norm R() of the embedded space X time satisfies (by assumption Rx
((++) R (1+ R$) M
= RCO + 2R²
[ h:
we used that the spectral norm of a matrix is at most its fg-norm.
We assume a worst-case where R(() grows monotonically at maximal rate. By the modified perceptron algo- rithm and choice = R²h.
| $ (((((()))) 2Bh) s V3R
11

---

Under review as a conference paper at ICLR 2020
By choice of and assuming 1 S 20R2 /yP
R - R(!) + +2V3R3 RV S R(1)
2v60
R(1) 1 yA/R²
1002
Solving the above recursive equation, holds for all 20RR2/P2.
R!
2v60 1002
M/R²)
R exx
[00600
y /R
R s 2R.
1002
Now, summing equation 8 we have
| -1
10
S 22V6R
since Σi_1 VV
So 20R² /r2 updates, the elements embedded by the network travelled at most 2-202/2 v6,2 < <0.05y². Hence, 1007
the samples the network received kept margin of 0.9y during training (by the assumption y 1). By choice of the loss function, SGD changes the output neuron as in the modified perceptron algorithm. By Theorem the
number of updates is most -22- 20R2 /y² So, the assumption on made during the proof holds.
0.99
THE MODIFIED PERCEPTRON
Proof of Theorem 2 Denote by w" the optimal separating hyperplane with ||w*]] 1. It satisfies yyu" -x 2 for all xg. By the definition,
wll) . = wil w" yaw -x; 2 yhr
and
| = | 1/ + 2y
x/ (1xx/)))) - (2Bh + (Rh))
By Cauchy-Schwarz inequality, 2 wl( w-/ |m00
So the number of updates is bounded by
2Bh + (Rh)2
(yh)2
At time the margin of any that does not require update is least
B
B
(2Bh + (Rh)2),
The right hand side is monotonically decreasing function of so by plugging in the maximal number of updates we see that the minimal margin of the output is at least
yBh
2Bh + (RA)
12

---

Under review as a conference paper at ICLR 2020
FIGURES
0:43
Traean syen 1el Freero Froo
Foaer syen 1el FroecaFre
04
g lyct 1e)
04
Teaiare Only Loyer 2- Thee Fry
0.33
Teakir Day 2: The Fry
0.
8
0.33
0:35
[T
co
x201
Epech
x22
(a) 30 input dimension
(b) 60 input dimension
Figure 2: Error during training for a sample size n.
(a) step size n
(b) step size n
(c) step size n
Figure Error during training for an input dimension and sample of size n 30.
0.3
Trae Onyy Loyer 2- be aroul Erxe
1000
200C
Epach
Figure 4: B = O: error during training for an input dimension and a sample of size 30.
13

---

Under review as a conference paper at ICLR 2020
0.7
Feckenscoolaii Inercalee
66
0.5
040
02
03
001
03
0.0
100
100
100
200
250
300
350
400
Epsch
(a) sample of size n
(b) sample of size nt
2.0
00
0.5
Empiiee wotiiiiliiieeee Crw
Bardor Bralsienn Emalrca Tsetre
02
0.2
toren Cop
Curnets
200
4C2
433
890
1030
1200
10
15
25
32
15
Fpoct
Egoth
(c) sample size n²
(d) sample of size n²
Figure 5: Parity: error during training for input dimension n = 20.
160
0.5
158
055
Oo kidu vallr Top Fow findess abalotion Expluitrer
Dur ao storlo
Drer
0.7
0.1
100
150
280
350
300
300
100
20
60
100
322
342
130
100
(a) sample of size
(b) sample of size n?
04-
0.5
Cariidattttoo The Cve furder vetibrrer The Eve"
Our instorer Emplrca sostbreen the Kestin detratinn Enprcel fatton Broadee E1a
13
0.
Epoth
(c) sample of size n
(d) sample of size n²
Figure 6: Random symmetric function: error during training for input dimension n = 20.
14

---

Under review as a conference paper at ICLR 2020
05
Emo rical Entr Trua Entrr
0.25
0.15
0 000000
1000
3000
Figure 7: Label error resistance. Labels of the sample were flipped with probability p= 10 Sample of size 10n whose input dimension is n = 30.
0.45
Fmoskw
0.4
0.35
033
Erner
0.25
8
0.15
2000
4000
10000
Epoch
Figure 8: Input Error resistance. All the entries of the vectors in the space were randomly shifted. Sample of size 10n whose input dimension 30.
15


Reviews:
[{"review_id": "H1gUil1TYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "The paper studies the problem of learning the class of symmetric boolean function, that is, functions that depend only on |x| = \\sum_i x_i. The paper shows that with proper initialization, one-hidden layer over-parametrized networks can learn this class of functions. The main observation that the authors make is that the last layer weights are updated as in the Perceptron algorithm and as long as the first layer has learned a large-margin representation, the first-layer weights do not change much. The authors experimentally validate their theory and additionally show that random initialization fails to converge to a low test-error solution while their special initialization works.\n\nOverall, the main complexity arises from handling training of both layers and this is cleverly analyzed. However I am leaning towards rejection as the underlying problem does not seem well-motivated. The class of symmetric boolean functions can be modeled as a univariate function by mapping x -> |x| which is easy to solve in the no noise setting analyzed by the paper. Also, in terms of learning with neural networks, as the authors point out, one can learn this class by training only the last layer. It is unclear why this setup warrants the use of a neural network for training. The problem would be more challenging and interesting for the class of symmetric (permutation invariant) functions on the real domain where using symmetry in the architecture/initialization can potentially give gains.\n\nWriting - Proofs are mostly clear however it would help to add more details in the proof of the main theorem (especially to argue about the use of the Perceptron convergence theorem for the changing representations). Also, the introduction needs to further motivate the setup and its relevance to neural networks.\n\nRepresentation - Regarding the representation for indicators using ReLUs, one could use a simpler and more standard representation. In prior work the indicator is represented using a difference of ReLUs, 1[|x| >= i] = ReLU(|x| - i + 1) - ReLU(|x| - i) and 1[|x| = i] = 1[|x| >= i] - 1[|x| >= i+1] = ReLU(|x| - i + 1) - 2 ReLU(|x| - i) + ReLU(|x| - i - 1). Now one can express \\sum_{i \\in A} 1[|x| = i] by summing up these indicators and adding a bias term of -0.5 will make the sign be the correct value. Note that this would overall require only n + 2 hidden units with the weights now being bounded by constants. This would still have a margin of \\Omega(1/n). Is there a particular reason for the choice of representation in the paper?\n\nExperiments - The plots are hard to parse and inconsistent. Firstly, it would be better to use line plots instead of scatter plots to highlight the trend. Secondly, the x-axis needs to be sampled more frequently. The number of epochs seem to be varying in the experiments, please make that consistent. Lastly, the important plots need to be moved to the main paper. Are the experiments for multiple runs or just a single run?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkg_Pp2rcB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "PAPER SUMMARY: This paper studies the problem of training a single hidden layer neural network to represent an arbitrary symmetric function. These are functions $f : \\{0,1\\}^n \\to \\{-1, 1\\}$ which are invariant to permutations in the input coordinates. The authors' main result (Theorem 1) shows that if you take a single hidden layer network with $O(n)$ hidden units and initialize the weights in a particular way, then for any symmetric $f$, SGD training will converge to an empirical risk minimizer with guaranteed small generalization error. On the other hand, the authors' experiments suggest that arbitrary symmetric functions are not learnable from random initialization. Taken together, these results point to the importance of designing network architectures/ initializations that respect the structure in the function class you're trying to represent.\n\nREVIEW SUMMARY: I lean towards rejecting this paper however, because I am not convinced of the results' significance. We already know how to learn symmetric functions (see Exercise 3.26 in Mohri et al., 2018). The authors' results show that we can inject this knowledge into a neural network at initialization, and then run SGD without making things too much worse. I do not see how these ideas might apply to more substantial learning problems where our prior knowledge is less precise. Moreover, while the proofs are clearly presented overall, I have one concern with a key step in Lemma 4.\n\nMAJOR COMMENTS:\n\n1) The key property of symmetric functions is that their output depends only on $|x|$. Thus, one can first extract \"cardinality features\" $x \\mapsto |x|$, after which learnability follows by standard generalization theory results (as the authors note in the proof of Theorem 1).\n\nThe basic idea of Theorem 1 then seems to be to realize this feature map as the hidden layer of a single hidden layer ReLU network (this is essentially what the initialization does) and then show that running SGD will not move the weights too far from the initialization (Lemma 4).\n\n(a) First, I think it would be helpful to the reader if the authors could make this intuition more explicit. In the submission the authors do not give much explanation for the choice of initialization.\n\n(b) Second, because this is a learning problem we already know how to solve, the results seems a little contrived. I do not see how these ideas could extend to more challenging cases where our prior knowledge of symmetry (e.g. translation invariance) does not by itself lead to an algorithm with efficient learnability guarantees.\n\n2) I could not follow one step in the proof of Lemma 4 (used to show that SGD does not move the weights too far from the initialization). Why does Theorem 2 imply that the number of updates is at most $20 R^2 / \\gamma^2$? In Theorem 2, $R$ is fixed whereas in Lemma 4 it varies with $t$. To me this seems important, since without a bound on the number of steps it is unclear how you can control how far the embeddings move.\n\nMINOR COMMENTS\n\n3) In the statement of Lemma 4, linear separability of $V$ should be with respect to some fixed partition $Y$?.\n\n4) In Figure 5, why is empirical error not decreasing over epochs?\n\n5) I think the figures referenced in the text should be in the paper, not the appendix.\n\nMohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning. MIT press.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The two main concerns raised by reviewers is that whether the results are significant, and a potential issue in the proof. While the rebuttal clarified some steps in the proof, the main concerns about the significance remain. The authors are encouraged to make this significance more clear.

Note that one reviewer argued theoretical papers are not suitable for ICLR. This is false, as a theoretical understanding of neural networks remains a key research area that is of wide interest to the community. Consequently, this review was not considered in the final evaluation.
Decision: Reject