Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

REVIEW 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.

MAJOR COMMENTS:

1) 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).

The 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).

(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.

(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.

2) 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.

MINOR COMMENTS

3) In the statement of Lemma 4, linear separability of $V$ should be with respect to some fixed partition $Y$?.

4) In Figure 5, why is empirical error not decreasing over epochs?

5) I think the figures referenced in the text should be in the paper, not the appendix.

Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning. MIT press.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.

Overall, 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.

Writing - 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.

Representation - 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?

Experiments - 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?
review_title: Official Blind Review #2

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