Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In order to formalize the intuition that neural nets learn by building hierarchical features, this paper considers a model of learning Boolean functions shoe spectrum satisfies a certain  "staircase" structure. Roughly speaking, for every non-zero coefficient in the support, there is a subset of it that also has a non-zero coefficient. This paper shows that a certain family of neural networks will successfully learn such functions. In contrast, earning parity functions along is hard.   
main_review: The strength of the paper is that it comes up with a nice clean abstraction of hierarchical structure in functions, and proves an elegant theoretical result, which is borne out by practical experiments. 

One can ask whether this structure really models the more complex kind of structures you would find in images etc. It is hard to argue too strongly here and the paper does not try (which is fine, this simpler setting means you can actually give formal guarantees). 

However, one could still ask if the class of Boolean functions that they consider is a rich and natural class. How does it relate to other known classes of Boolean functions (halfspace, dnfs, decision trees, monotone functions etc). Is it known to include any class of functions that has been studied previously in the literature? I would have like to see the paper make a stronger case for this.  I don't think structure in the Fourier space lone qualifies a class  as natural. 

There are some other choices that struck me as a little non-standard, including the choice of squared activation functions and the architecture. The authors do discuss these under limitations.

Overall, I liked reading this paper. I thing it makes a nice contribution towards a rigorous analysis of how hierarchical concept learning happens. I will be wiling to support it more strongly if the case can be made that this is a natural and interesting class of functions.

 In general the writing is good, except there seems to be a typo/omission at a rather crucial place. If you look at line 164, the affine transform $A$ is not used anywhere in the definition. I suspect it was intended to be used in defining the sequence $h_k$. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper discussed the learnability of function by neural networks.

The paper introduces a "staircase function": a boolean function composed of monomials of increasing order such that higher order monomials are recursively composed of lower-order monomials. The authors argue that this is a prototype of a hierarchical feature structure present in natural data, and they show by experiment that this function, unlike a parity function, is efficiently learnable by standard ReLU MLPs.

The paper extends the formally the staircase function to a class of "Hierarchical Boolean Function" which it further extends to continous functions. As its main theoretical result, the paper introduces a somewhat non-standard neural network architecture and proves that it can efficiently learn hierarchical boolean functions under sparsity conditions, using a non-standard neuron-wise training algorithm.

main_review: The paper provides an interesting learnability result which attempts to further our understanding on why neural networks seem to learn natural data even though some simple synthetic functions such as parity functions are hard to learn.

The authors argue that natural data is better understood as having "staircase" hierarchy, where more complex factors are composed of simpler factors enabling a neural network to learn them in sequence starting from a linear-like model and increasingly adding non-linear factors. This claim is not proven, as it would hard to, but empirical evidence is presented in the form of the interpretable hierarchy of features that is sometimes observed in the layers of trained neural networks. The authors mention the NTK regime where neural networks behave non-hierarchically, however they fail to mention practical cases where non-hierarchical behavior is observed (e.g. training example memorization even with completely noisy labels). 

The theoretical proof has the benefit of considering a homogeneous architecture and initialization, unlike previous work, however the architecture and traning algorithm are still non-standard, so they don't necessarily transfer to practical neural networks.

Overall I consider the findings of this paper interesting although not groundbreaking.

EDIT:

I'm satisfied with the authors response, I've increased my score.
limitations_and_societal_impact: I'd like more discussion of how the paper claims reconcile with the observed non-hierarchical behavior.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors prove a theoretical result on the ability of deep neural networks to learn hierarchical boolean functions. Intuitively, the authors argue that neural networks are able to learn functions that contain low-level features that can be hierarchically combined into high-level features (aka staircase property).
main_review: **Disclaimer**: I am not an expert in the are of this paper (boolean functions and deep learning theory). Consequently, I had a hard time reviewing this paper. I try to make useful comments about the paper, but assign a low confidence score to my review. 

## Overview

The paper presents an interesting view on generalization in deep learning. In particular, I have not previously seen a similar analysis, even the results in Figure 2. I have seen arguments that neural networks learn functions of increasing complexity, as shown in Figure 2(d), but not in the application to boolean functions; the result in Fig. 2 (a), (c) are interesting: the network is unable to learn the function that lacks hierarchical structure.

My understanding is that the theory explains why NNs *can* learn the functions that have a hierarchical structure. Would the theory also predict that the network *cannot* learn a function that lacks hierarchical structure?

## Limitations

The main limitations of the work are probably that the model architecture (a sparsely and randomly connected network) and the training method (layer-wise optimization) are quite different from what is used in practice. 

## Clarity

The paper is quite technical, and not easy to follow for an outsider to the field. Even understanding the definition 1.1 was not trivial for me. Specifically, what are $M_1$, $M_2$? Are these just real-valued numbers? What is the intuitive meaning of $\hat g(S)$ being equal to zero? Overall, I would encourage the authors to provide more intuition behind definition 1.1 and other formal definitions in the paper.
limitations_and_societal_impact: The authors discussed relevant limitations of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper identifies a class of functions with hierarchical structures which can be efficiently learned by a neural network trained layerwise with stochastic coordinate descent. The authors introduce a sparsely connected neural network architecture and provide a corresponding layerwise training algorithm. Theoretically, they prove that for a class of hierarchical Boolean functions, the population loss can be minimized to be close to zero to illustrate the generalization ability.
main_review: Strength:

The motivation to study the functions with hierarchical structures which can be learned by neural networks is clearly described and the literature reviews are exhaustive. The generalization results for the hierarchical Boolean functions based on the population loss are quite strong. Numerical experiments on ReLU ResNets also support their claim. 

Weakness and comments:

The definition of the homogeneous neural network is quite different from the definition in [a]. It will be helpful to discuss the similarity and differences somewhere in the paper. Besides, it seems that the homogeneous neural network discussed in the paper is firstly studied by the reference [3]. However, the preprint [3] does not appear on its first author’s  website. It will be helpful to provide other easy-to-access references.

[a] Lyu and Li, Gradient Descent Maximizes the Margin of Homogeneous Neural Networks.

The organization of the paper can be improved. For instance, the general hierarchical architecture described in section 2 is rarely discussed in the rest of the paper. The authors may move this part into the appendix or discuss how the proposed neural network architecture, training algorithm, and generalization results can modify to learn functions with the general hierarchical architecture. 

The algorithm description is not very clear. Specifically, the authors only tell that each of the subroutine TrainNeuron runs SGD. They shall specify how many samples are drawn in each iteration and how many iterations SGD will be executed in the subroutine. Besides, it will be better to discuss the overall number of required samples in the training instead of directly stating the sample access to the data distribution. This will be helpful to generalize the results to learning general functions beyond those with the domain of {-1,1}^n.

The numerical comparison part is a bit confusing. The authors claim that they use the same ReLU ResNet. However, the architecture introduced in section 3.1 is not directly related to the ResNet architecture. The authors shall explain the relation between ResNet and the architecture in section 3.1.

Besides, the authors also say that they train the neural network using SGD instead of using their proposed layerwise training introduced in section 3.3. It will be helpful to provide the comparisons between these two training methods. The width of ResNet in the experiment is only 40. The authors may try testing on wider ResNet, for instance, 400.
 
Minors:

For the equation above line 165, y is not defined. I guess that it shall be defined by y=Ax+b. 

In line 172, the norm $\mathcal{S}$ is only defined via the pseudo metric $d_{\mathcal{S}}$. It will be helpful to properly define $\mathcal{S}$. 

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper studies hierarchical structures that can be efficiently learned by neural networks to formalize the intuition that deep learning works by building feature hierarchies. It was shown that a class of sparsely connected networks trained in a neuron-wise and layer-wise manner can learn hierarchical boolean functions as defined in the paper. As all the reviewers agree, the paper contains strong theoretical results towards this direction and I recommend acceptance.

However, please note that the writing and notation can be improved to make the paper more accessible for a wider audience. Please take into account the updated reviews when preparing the final version to accommodate the requested changes including the necessary clarifications and typos pointed out by the reviewers.

An additional typo/notation issue: In section 3.2, the regularized loss \ell_R is defined as the population loss. However, in the gradient calculation step of Algorithm 2, \ell_R is evaluated at a batch of data points. This seems like a notational error.
Decision: Accept (Poster)