The staircase property: How hierarchical structure can guide deep learning
Authors: Emmanuel Abbe
Enric Boix-Adserà
Matthew Stewart Brennan
Guy Bresler
Dheeraj Mysore Nagaraj
Venue: NeurIPS 2021 Poster (2021)
Keywords: deep learning
hierarchical
stochastic gradient descent

Abstract: This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the ``staircase'' property for functions over the Boolean hypercube, which posits that high-order Fourier coefficients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this  property can be learned in polynomial time using layerwise  stochastic coordinate descent on regular neural networks -- a class of network architectures and initializations that have homogeneity properties. Our analysis shows that for such staircase functions and neural networks, the gradient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that the staircase property has a role to play in understanding the capabilities of gradient-based learning on regular networks, in contrast to general polynomial-size networks that can emulate any Statistical Query or PAC algorithm, as recently shown.

The staircase property: How hierarchical structure can guide deep learning
Emmanuel Abbe
Enric Boix-Adsera MIT eboix0mit.edi
Matthew Brennan MIT
Guy Bresler MIT guy0mit. edu
EPFL emmanuel.c. abbe@epfl..e@ecccccccooo
Dheeraj Nagaraj MIT Cheerajemin edu
Abstract
This paper identifies structural property of data distributions that enables deep neural networks to learn hierarchically. We define the "staircase" property for funetions over the Boolean hypercube, which posits that high-order Fourier coeffi cients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this property can be learned in polynomial time using layerwise stochastic coordinate descent on regular neural networks a class of network architectures and initializations that have homogeneity prop- erties. Our analysis shows that for such staircase functions and neural networks, the muddient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that the staircase property has a role play in understanding the capabilities of gradient-basel learning regular networks, in contrast to general polynomial-size networks that can emulate any Statistical Query PAC algorithm, as recently shown.
Introduction
has been observed empirically that neural networks can learn hierarchically. For example, 'car' may be detected by first understanding simpler concepts like 'door', 'wheel', and so forth in intermediate layers, which are then combined in deeper layers (c.f. (12). However, on the theoretical side, the mechanisms by which such hierarchical learning occurs are not yet fully understood. In this paper we are motivated by the following question:
Can we identify naturally structured and interpretable classes of hierarchical functions, and show how regular DNNNs are able to learn them?
This is refinement of the generic objective of trying to understand DNNs: We identify several key desiderata for any theoretical result in this direction. (1) Natural structure: We aim capture naturally occurring data of interest, so the structural assumption must make conceptual sense. (2) Interpretubility: we hope to clearly interpret the inner workings neural networks, understanding both how they classify and also how they learn, then we need model for data that is interpretable to
this means network architectures and initializations that have homogeneity properties within layers, contrast the emulation architectures 4
Thee notion of regularity is specified in Definition 2.1
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

begin with. Interpretation of the representations occurring within a neural network is most clearly expressed with respect to structural properties of the data. Finally, (3) Regularity of the network: The network architecture and initialization should be symmetric in sense defined later on. This prevents using carefully-crafees
architectures and initializations to emulate general learning algorithms E We view this type of restriction as being partway towards considering practical neural networks that learn in a blackbox fashion. The results in this paper aim to satisfy all three high-level objectives. The relation with prior work is discussed in Section I.I
This paper proposes a new structurally defined class of hierarchical functions and proves guarantees for learning by regular neural networks. In order to describe this structure, we first recall that any function f :f+1,- - 11" + R can be decomposed in the Sourier-Walske basis as
[(x) = Σ f(S)xs(x), where f(5) = (sxs),, Xs(x) = II Z2
(I)
SC(m]
IES
and the inner product between two functions is (S.g) = (X))) for X ~ -1
This decomposition expresses (1) as a sum of components, each of which is a monomial (x).
weighted by the Fourier coefficient f(S). Our definition of hierarchical structure is motivated by an observation regarding two closely related functions, "high-degree monomials" and "staircase
functions", the latter of which can be learned efficiently and the former of which cannot.
Monomials with no hierarchical structure The class of monomials of any degree k where k S
n/2 (i.e., the class {xs) ((() is efficiently learnable by Statistical Query (SQ) algorithms if and only if k is constant [5] []. and the same holds for noisy Gradient Descent (GD) on neural nets with polynomially-mann many parameters [5], and for noisy Stochastic Gradient Descent (SGD) where the batch-size is sufficiently large compared to the gradients' precision R This was also noted in (77 which shows that gradients carry little information to reconstruct Xs for large |S], and hence gradient-based training is expected to fail. Thus, we can think of component Xs as simple and easily learnable if the degree [S] is small and complex and harder to learn if the degree |S] is large.
Staircase functions with hierarchical structure Now, instead of a single monomial, consider the following staircase funetion (and its orbit class induced by permutations of the inputs), which is sum of monomials of increasing degree:
Sa(2) 21 + œ1 + Z1 + 2I + +
X1sk
(2)
Here Sg(x)) has hierarchical structure, where 21 builds up to 222 which builds up to 2 22 and so on until the degree-k monomial Xisk. Our experiments in Fig. 2 show a dramatic difference between learning single monomial X and learning the staircase function Sp. Even with n = 30 and h = 10, the same network with ReLU ResNet layers and the same hyperparameters can easily learn Sy to a vanishing error (Fig. 2b) whereas, expected, it cannot learn X1:k even up any non-trivial error since X1:k is a high-degree monomial (Fig. 2a).
An explanation for this phenomenon is that the neural network learns the staircase function Sx(x) by first learning a degree-1 approximation that picks up the feature 21, and then uses this more readily learn 2 approximation that picks up the feature 21 and so on, progressively incrementing the degree of the approximation and 'climbing the staircase' up to the large degrees. We refer to Fig. Ia for an illustration. This is indeed the learning mechanism, as can see once we plot the Fourier coefficients of the network output against training iteration. Indeed, in Fig. 2c we see that the network trained to learn X1:10 cannot learn any Fourier coefficient relevant to X1:10 whereas in Fig. 2d it is clear that the network trained to learn S10 learns the relevant Fourier coefficients in order of increasing complexity and eventually reaches the X1:10 coefficient.
Main results We shed light on this phenomenon, proving that certain regular networks efficiently learn the staircase function St (æ),, and, more generally, functions satisfying this structural property:
Definition 1.1 (Staircase property). For any M > 1, a function g : (-1,1) - R satisfies the
(1/M, MD -staicasse property over the unbiased binary hypercube if:
for all S C [n), if (S) + then [,(S) [1/M,
for all S C [m), if @(S) # and |S| 2 there is S' S such that |S\ SS and @(S') + O.
Furthermore, g is said to be s-sparse polynomial if((S ((S) # 0}1 S
2

---

Input
Neura Network
Oulpur
Oupui
Layer
Lasar
Starcase Fundiion
(a) An illustration of hierarchical learning where cessive layers build upon the features from previous layers.
(b) An illustration of the proposed architecture. The solid blue and grey represent sparse random connections
Figure 1: Hierarchical learning method and proposed architecture.
Learning
Generotzat on Enor Yuu
Generaization Emor for 8/
Denerottoeton bortoon Emvor
2.8
SGD Haration
SGD Heeaiion
(a) Loss Evolution for Learning Parity
(b) Loss Evolution for Learning $10
er Confficienaa Learning Xo3
12
Fourier Coeficionts Learning S.,
Ls
Douneet Contont
4.25
200
2010
1201
800 Teration
(c) Fourier Coefficients for Parity
(d) Fourier Coefficients for Siu
Figure 2: Comparison between training X1:10 and S10 with 30 on the same 5-layer ReLU ResNet of width 40. Training is SGD with constant step size on the square loss. Here fiss denotes the Fourier coefficient (Xtés f) corresponding to the network output f.
The parameters M and appear naturally since PAC-lcarning algorithm for s-sparse polynomials satisfying the [1/M, -staircas property must use a number of samples that depends polynomially on M and s. Our theoretical result is informally summarized as follows, and we remark that the proof shows that the neural network progressively learns approximations higher degree:
Theorem 1.2 (Informal statement of Theorem 2.2
Let [-1, + R be an unknown s-sparse polynomial satisfying the [1/M, -staircas property. Given access to random sumples from ((x, s(x))))aa4-11..) j= there is regular neural network architecture that upproximately learns g in poly(n, .)) time and samples when trained with layerwise stochastic coordinate descent.
Even though we only consider hierarchical functions over the Boolean hypercube {-1, 1}" th in our theoretical result, believe that the techniques used in this work can be extended other function spaces of interest, exploiting the orthonormality of the corresponding Fourier basis functions. For this reason we give fairly general definition of hierarchical functions in Section 3 that goes beyond the Boolean hypercube, class of functions is of further interest because it includes as special cases well-studied classes such biased sparse parities and decision trees in a smoothed complexity setting (see Section 3.1
well as beyond the strict notion of increasing chains. This more general

---

1.1 Related Work
Statistical query emulation results For the general class of polynomial-size neural network ar- chitectures with any choice of initialization, it is known that SGD sufficiently small batch-size can learna any function class (including functions satisfying the staircase property) that is efficiently learnable from samples [3]. while GD can learn any function class that is efficiently learnable from statistical queries (SQ) 4. However, these results rely on highly non-regular architectures and initial- izations, with different parts of the nets responsible for different tasks that emulate the computations of general learning algorithms. In particular, it is not known how to obtain the emulation results of A for "regular" architectures and initializations as defined in Definition 2.T In contrast, our architecture in Theorem 2 is a regular neural network in this sense, and our analysis further illustrates how features are built greedily over depth rather than by emulating given algorithm.
Consider also the orbit class under permutations of the inputs of the "truncated staircase function"' = (z), for 1 j S k S n. Note that this class is efficiently SQ-learnable when k = n. since the monomial X1:. is always present and one can recursively check which sub- monomial present or not by checking at most n monomials at each step. However, we conjecture that Sj-> (4) is not learnable by regular networks trained with gradient descent if min(n j.j) = w(1). Therefore such truncated staircases provide a candidate for separating gradient- learning on regular networks versus general, non-regular networks that allow for emulating any SQ algorithm [+]
Hierarchical models of data Explicitly adding hierarchical structures into machine learning algo- rithms such as hierarchical Bayesian modeling and hierarchical linear modeling has proved successful in various machine learning tasks beyond deep learning R M. For image data, [ 33 propose hierarchical generative models of images and use them to motivate deep convolutional architectures, although these works do not prove that deep learning learns these generative models. 14 similarly
proposes 'deep rendering model' which hierarchically models levels of abstraction present in data, but does not prove learnability. (15) gives training algorithm for deep convolutional networks that provably learns a deep generative model of images. The paper [16] proposes a generative model of data motivated by evolutionary processes, and proves in a formal sense that "deep" algorithms can learn these models, whereas shallow algorithms cannot. In contrast to our work, the "deep" algorithms considered by [6 are not descent algorithms on regular deep neural network architectures. In [17] it is shown that during training of two-layer ReLU networks with SGD, the lower frequency components of the target function are learned first. Unfortunately, their results have an exponential dependence on the degree. In our work, we leverage depth and the hierarchical Boolean function structure to ensure that higher-level Fourier coefficients are learned efficiently. Finally, [ studies learning Boolcan circuits of depth Olog n.) via neural networks under product distributions using layer-wise gradient descent. While [8] requires the architecture to match the Boolean circuit being learned, in contrast, our architecture is regular and independent of the function learned.
Power of depth Several works have studied how representation power depends on depth. 19 shows that deep networks can represent class of compositionaalyycreeate functions more efficiently than shallow networks. 20 shows that certain smooth radial functions can be easily represented by three-layer networks but need exponentially-men many neurons to be represented by two-layer network. Based on an analysis of learning fractal distributions related to the Cantor set, [1 conjectures that if shallow networks are poorly represent target function, then deep network cannot be trained efficiently using gradient based methods. [22 presents a depth separation result by showing that deep networks can produce highly oscillatory functions by building the oscillations layer by layer. (23 uses this phenomenon to show a sharp representation theorem for arbitrary-depth ReLU networks.
Other theoretical works have proved depth separation theorems for training. [24] prove that two- hidden-layer neural network where the first hidden layer is kept random and only the second layer is trained, provably outperforms a just one hidden layer network. In [25 26 it is proved that deep networks trained end-to and-to-end with SGD and quadratic activation functions can efficiently learn a non-trivial concept class hierarchically, whereas kernel methods and lower-depth networks provably fail to do so. The class of functions studied by [25] 26 are those representable as the sum of neurons in teacher network that is well-conditioned, has quadratic activations and has depth of at most log log n. where n is the number of inputs. This function class is expressive but incomparable to the hierarchical function class studied in work (e.g., can learn polynomials up degree n,
2 These reductions are for polynomial time algorithms and for polynomial precisions the gradients.

---

whereas 22 is limited to degree log(n)). Furthermore, our function class has the advantage of being naturally interpretable, with complex features (the high-order monomials) being built in a transparent way from simple features (the low-order monomials). In for the simplified case of deep linear networks, where an 'incremental learning' phenomenon observed in which the singular values are learned sequentially, one after the other. This phenomenon reminiscent of the incremental learning the Fourier coefficients of the Boolean function in our setting (Fig. 2). For real world data sets, E0 empirically shows that in many data sets of interest, simple neural networks trained with SGD first fit a linear classifier to the data and then progressively improve the approximation, similar in spirit to the theoretical results in this paper.
2 291, gradient dynamics are explored
Neural Tangent Kernel and random features of overparametrized (or Neural Tangent Kernel regime) neural networks to the global minimizer of empirical loss when trained via gradient descent. In this regime, they show that neural networks behave like kemne methods and give training and/or generalization guarantees. Because of the reduction to kernels, these results are essentially oon-hierarchical. 61 52 in fact show that deep networks in the NTK regime behave better than shallow networks. We refer to [26 for a review of the literature related to NTK and shallow learning. Finally, we mention the related works 33 which consider learning low-degree (degree g) polynomials over R", without a hierarchical structure assumption. They require n
sequence of papers have studied convergence
( neurons to learn such functions, which is super-polynomial once q >>>> 1. The results hold in the random features regime, known to weaker than NTK.
1.2 Organization
In Section we give the problem setup, network architecture and the training algorithm, and also state our rigorous guarantee that this training algorithm learns functions satisfying the staircase property. In Section g we discuss possible extensions, defining hierarchical functions satisfying the staircase property in greater level of generality from Definition I.1 We refer Appendix A additional experiments which validate our theory and conjectures for both the simplest definition of the staircase property in Definition I.I and the generalizations in Section 3.2
2 Regular networks provably learn hierarchical Boolean functions
We state our main theoretical result, which proves that a regular neural network trained with descent algorithm learns hierarchical Boolean functions in polynomial time.
2.1 Architecture
Our network architecture has neuron set V and edge set E, and is defined as follows (see also Fig. Ib]. The neuron is V Vnn V1 U... Vz. Here V {Van,o Uin,1..... Vin,n J of + inputs, and each intermediate layer consists of [V = W neurons. Furthermore, the edge set E is sparse, random subset of all possible directed edges:
each (Vo, 04) E Vin V4 is in the edge set E independently with probability Pr, and each (2,, u++1) E V, x Vi+1 for i E [L 1] is in the edge set E independently with probability P2-
For each edge e E, let there be weight parameter ae E R. And for each neuron v E V Vnn. let there be a bias parameter b, E RR. The parameters of the network are therefore E R and b E IR Vi, For simplicity of notation, we concatenate these two vectors into one vector of parameters
w w==e ia b] E R 4 VVL.
For each i E [n), the ith input, Vin E Vin computes 2,, and the 0th input, Un..0 computes a constant: Son.. (x; Iú. and Sum. (x; = 1.
Given a neuron v E V V Vin. the function computed at that neuron is a quadratic function of a linear combination of neurons with edges to (i.e., the activation function is quadratic). And the output of the neural network is the sum of the values of the neurons at the intermediate layers:
w)( =
Σ (=(L))E
aefu(x;
+ b.. and f(z;w)= = Σ fa(x;w).
VEVVV
5

---

Our architecture satisfies the following regularity condition:
Definition 2.1 (Regular network architecture and initialization). An architecture is regular for any 1 S S I L, for any distinct pair of potential edges (vi, vj), (1/, v/) V; Vj, the events that these edges are in are i.idd;; the same holds for any distinct pair of potential edges [u, vz), (u', v/)) E Vin Vji the same holds for any distinct pair of potential edges (u, Vout), (u', Tout) V2 X Vout (where Vout. is the outpul vertex). Furthermore, the initialization is regular if it is L.dd over the set of present edges and each weight has symmetric distribution.
In our case the weight initialization is i..d. and symmetric since we choose it to be identically zero everywhere, which works since we escape saddle points by perturbing during training. On the other hand in our experiments the initialization is an isotropic Gaussian, which also satisfies Definition 2.1
2.2 Loss function
Let the loss function be the mean- leaan--qured-erss between the output f of the network and a function
g: (-1, 13" R that we wish to learn. Namely, for any (-1,1]", R and b IR VAV, define the point-wise loss and population loss functions respectively, where w = [a, bj:
((:; w) -)
- g(x))² ((w) = (u))=11--1.))0012::::
(3)
We will train the neural network parameters minimize an Iæ-regularized version of the loss function. Let A1 A2 > be regularization parameters, and define the point-wise regularized loss (r((:; E(2; w) + R(w) and the population regularized loss (n((w ((w) R(w). where
R(w) = Σ
1
Σ
A2a
2
2
c=(u,))EB uVVi
c=(u,))E ugVinn
The distinct regularization parameters λ1 A2 > 0 for the weights of edges from the input and previous-layer neurons, respectively, are for purely technical reasons and are explained in Section 2.5
2.3
Training
We train the neural network to learn a function ( 1-1, - R by running Algorithm This algo- rithm trains layer-wise from layer layer L. The ith layer is trained with stochastic block coordinate descent, iterating through the neurons in VG in an arbitrary fixed order, and training the parameters of each neuron E Vi2 using the TRAINNEURON subroutine. Each call of TRAINNEURON runs stochas- tic gradient descent to train the subset of neural network parameters W. {aa)e=ter ==(,,)) U (b,) directly associated with neuron (i.e., the weights of the edges that go into v, and the bias of v), keeping the other parameters w- {ae fe= ('))) W/)E s.t. uste' U {br (VEV fixed.
Algorithm 1: TRAIRRANNTTE TRRIINNTTWRRKLLYEERR
Input: Sample access to the distribution {(r, g(z))) ((z))) (-1,1, Hyperparameters W, L. P2, Å1, X2, 1), B, Cstop. a, T.
Output: Trained parameters of neural network after training layer-wise.
(V, E) t random network constructed as in Section 2.1
n Ō 0
// Initialize all weights and biases zero.
3 for layer ioveri=11 to L do
for neuron v V; do
11 Train the neuron parameters, Wo fixing other parameters w + TRAINNEURON(), w'; Å1 d2 B, Estop, T)
f 1-t+1
end
end
Return !

---

Algorithm 2: TRAINNEURON UU w X1, X2, 7) B, Cstop: 02; 7)
Input: Neuron V Vín Initial network parameters w Access random samples (())( for ~ ~ (-1, 1 Hyperparameters λι A2, B, Estop,
Output: Parameters of network after the subset of parameters w, of neuron perturbed and then trained with NEURONSGD, while all other parameters w-v remain fixed.
// To avoid saddle points, randomly perturb the neuron parameters weerburb f wa where is noise vector whose entries are i.i. in (ni)((-n..))) wperturt f [w0 weeeturb]
// Run stochastic gradient descent on neuron parameters, until approximate stationarity
w SGD NEURONSGD(t: e weeettub X1, A2, B, Estop; a)
// Prune the neuron's small weights
wround t WSGD rounding 0 every entry of magnitude less than Return wound
[w" w [ound]
Algorithm 3: NEURONSGD(c. (c, w A1, A2, TJ, B, Estop: a. T)
Input: Neuron V E V. Van Initial network parameters wo Access to random samples (ær, gx))
for ~ {-1, 1).". Hyperparameters λ1, A2, 37, Catop;; a.
Output: Parameters of network after the subset of parameters w, corresponding to neuron v trained, all other parameters w-. remain fixed.
1 +- 0
while true do
// Approximate Ve,eR with minibatch size B Draw i.i.d. data samples (r+1 (0f11g((""))) g(xx"))),.... B (r*B,,(xx.B)) B(x)
e' < ΣE Vw, (n w!)
// Stop if have reached an approximate stationary point
if ||55 S. estop then break out of the loop;
// Update We in direction of the approximate gradient
w w - a
t --t+1
Return [wo w
2.4 Theoretical result
We prove that Algorithm I learns functions satisfying the staircase property in the sense of Defini- tion
We defer the exact bounds on the parameters considered Appendix B
Theorem 2.2. Let g: (-1,1)) + R be an unknown s-sparse polynomial satisfying the [1/M, M]- staircase property for some given 8, M > 1. Given an accuracy parameter e > 0, a soundness parameter 0 < < 1, and access to random samples from {(x, ((z))))=(-1111)- there is a setting of hyperparameters, for Algorithm 7 that is polynomially-bounen bounded, i.e.,
1/ poly(n, M, 1/e, 1/5) S W. L. P1, P2, A1, 22, B, Estop, a, S poly M, 1/8,, such that Algorithm 1 runs in poly(n, s, M, 1/e, 1/8) time and samples and with probability returns trained weights w satisfying the bound {(w) S c on the population loss.
2.5 Proof overview
We now briefly describe how Agorithm[leaat giving high-level depiction of the training process in the case that the target function the staircase function Sa(x) = æ1 + I T1 2122233 We refer to Fig. 3 for illustration of the training procedure, where grey neurons are 'blank' (i.e., have identically zero output) and the green neurons are 'active' (i.e., compute non-zero function). Initially all neurons blank and the total output of the network is 0.
7

---

X/3
3,4
Linear Layer
R3
Linear Layer
Layo Thea layer
X2
3/2
712
12
%1
X1
X1
72
1
Output: 3g
Output: Rg
Output: 3y305
Input
Step 1
Step 2
Step 3
Figure 3: An illustration of the training procedure for learning Sz(æ) I1 + 21 + 212233. The grey neurons are 'blank' and the green neurons are 'active'.
We set the random network topology connectivity hyperparameters P1 and P2 to be small, so that the network is sparse. We can show that the following invariant is maintained throughout training: any neuron has at most two active parents. Intuitively, this because we can bound the number of active neurons at any iteration during training by
+ 1, so the number of neuron tuples (u1, u2, Mg, v) V such that U1, U22 ug are active and all have edges to v is in expectation bounded by (s + + (p1) W < 1. Since any neuron during training has most two active parents, may tractably analyze TRAINNEURON for training new neurons: in a key technical lemma, we show that every active neuron has exactly two active parents and u', and approximately computes monomial given by the product of the parents' values, (x( = Xs. R fu(x)
We cannot set P1 and Pa to be too small or else the network will not be connected enough to learn. Thus, we must also the connectivity parameters so that for any pair (u, u/) E Vn x (V Vt.), the neurons and u' share many children, and at least one of these children may learn the product if it is very large.
useful. For this is sufficient to take the expected number of shared children p1p2 W >
We now present run of the algorithm, breaking it up into "steps" for exposition.
The algorithm iterates over neurons and trains them one by one using TRAINNEURON. Most of the neurons trained are left blank: for example, if a neuron v has the two inputs x2 and 1, then by our key technical lemma the neuron could either remain blank or learn the product of the inputs, I2 x2 1. But the mean-squared error cannot decrease by learning 22, since is orthogonal to the staircase function in the L2 sense (i.e., (5)( x222 = Ó, because the staircase function does not have 22 as a monomial), so the neuron e remains blank. Let t, be the first iteration at which algorithm reaches neuron ni E V1 that has 2 and 1 as inputs. When the network trains mi using the sub-routine, we show that it learns to output function to S1(rr) that n4 can output. Combined with the linear layer, the overall neural network output becomes f(;; w²x) z Z1-
Step 1:
x1 1, since that is the highest-correlated
Step The error function after Step is E1 S2(x) -xx wh1 2122 31 Again, for many iterations the training procedure keeps neurons blank, until at iteration ty it reaches a neuron n2 with inputs X1 (due to neuron n1) and x2 (directly from the input). Similarly to Step 1, when we train n2, we show that it learns to output 22 which is the function with highest correlation to E, (x) which n2 can output. Thus, the neural network now learns to output fæ; w²*) = x1 + 21 so the error function has decreased to E2(x) S2(x)) f(x; w²2) RS 1232.3 The training proceeds this manner until all monomials Sz(x) are learned by the network.
Error Propagation and Regularization: A significant obstacle in analyzing layer-wise training that outputs of neurons are inherently noisy because of incomplete training, and the error may grow exponentially along the depth of the network. In order to avoid this issue, we have two distinct regularization parameters λ₁ A2 and connectivity parameters P1, Pa for edges from inputs versus edges from neurons. In our proof of Theorem 2.2 we set A & X2 and P1 >> P2, which ensures that after training neuron (say n2 above) the weight from the neuron nı (which has regularization parameter X2) is much smaller than the weight directly from the input I2 (which has regularization parameter A1). Since the inputs are noise-free, this disallows exponential growth of errors along depth. We conjecture that if the network is trained end-to-end instead of layer-wise, then one can avoid this technical difficulty and set A = X2 and P1 = P2, because of backward feature correction phenomenon 26 where the lower layers' accuracy improves higher levels are trained.
8

---

3 General Hierarchical Structure
3.1 Extension to biased binary inputs and implications
We extend the main result of this paper to more general setting of functions over space of i.i.d. binary variables that have zero expectation but are not necessarily supported on {+1, -1.. For instance, if [X.)iejm) are i..d. and Boolean (on {+1,- -1}) with ((x)) = for some b E [-,, the centered variables X; = X; b are valued in {1 b, -1 b}. Over these centered variables, the Fourier coefficients of function are given (up normalization) by f(S) = f(x) Iliss X, for any S C [n]. Thus, the staircase property of Definition 1.1 generalizes clearly: the function f: {1 -1-00 b, 11 -1 b}" + R satisfies the staircase property if for any S C [nx] with |S| 2 2 such that f(S) # 0, there is subset S" C S such that |S \ 5" = 1 and f(5") + 0.
Showing a similar result to Theorem 2.2 for staircase functions on the variables X, with a quadratic activation requires a slight modification of our argument since X? is no longer constant (and equal to 1), so one cannot the simple identity Z, Z2 (Z) + 2
1 that holds for variables valued in {+1,- -1] to prove that a neuron learns the product of its inputs when trained. However, adding skip connections from the previous layer with quadratic activation, along with the fact that r172 ((r) +r2)²- r r2)/2, one can hierarchically learn new features as products of previously- learned features. Alternatively, one can change the activation so that each neuron maps vector input to (a + 6)2² + c. y² where a, b, C are trainable parameters, to learn products of general binary variables. similar proof to that of Theorem 2.2 is then expected to hold, implying that one can learn staircase functions over i.i.d. random variables that are binary and centered (beyond (+1,-1] specifically). We will now discuss two interesting examples that fall under this setting.
Biased sparse parities and kernel separation Consider the problem of learning sparse biased parities, i.e., the class of monomials of degree log(n) with (+,,-1)-var -vaalue input distribution that is i.i.d. with IEX; = b = 1/2. It is shown in [36) that such a distribution class is not learnable by any kernel method with poly-many features, while it learnable by gradient-based learning on neural networks of polynomial size. The result of (36) relies on an architecture that allows emulating an SQ algorithm far from regular network as considered in this paper. However, sparse biased parities are staircase functions over unbiased binary variables, with polynomially-mant nonzero coefficients since the degree logarithmic. So an extension of Theorem 2.2 to arbitrary binary centered variables would imply that regular networks can learn sparse biased parities, implying a separation between kernel-based learning and gradient-based learning on regular networks.
Decision trees under smoothed complexity model Secondly, in a smoothed complexity setting, where the input distribution is drawn from the biased binary hypercube, and the bias of each variable is randomly chosen, the class of (deptth decision trees satisfies the general staircase property. This is because Lemma 3 in 37 implies that with high probability there is a poly(n/ee-spp) )spaase polynomial that e-approximates the decision tree and satisfies the staircase property over the biased binary hypercube. Thus, the extension of our result to the case of biased binary inputs would imply that regular neural networks learn decision trees in the smoothed complexity model B
3.2 Extension more general L2 spaces
We now give even more general version of the staircase property in Definition 1.1 Since neural networks are efficient representing affine transforms of the data and smooth cow-dimessional functions 35 we generalize the class of hierarchical functions over the space of continuous, real valued functions [-R, R(" C R"; R E R+ U (oo) without any reference to underlying measures but with enough flexibility to add additional structures like measures and the corresponding 1,2 norms. Set R E 1 U } and consider any sequence of functions H := (h+= R -> IR. ] such that ho is the constant function 1, and any affine transform A R -> R such that A(x) = Ax b for A E b E R" We call function f: [- R, Rjj IR be (H, -ppolynomma if there exists finite index set I C (N U (0))" such that for some real numbers (onk (on)ket,;
f(x) = Ex. On I (v:)
"Such conjecture was recently made by 38 which leaves as an open problem in Section 1.3 whether neural networks learn log(n) (og(nn)jjunts in smoothed complexity setting, and implicitly poses the same problem about the more general case of (og(n))-epp decision trees.

---

Where = A(x). We also define (rd(k) := l k2s * OH and partial order "=" over (N U {OH)" such that k' k iff k E {0, k for every i [n]. For M 2 1, we will call A),,yy) to be (1/M, M) hierarchical if
1. 1/M Σ |ak] S .M for every k E 1y.
2. For every I such that (rd(k) 2 2, there exists k' E such that Ord(k') Ord(kk) -1
and k' 3 k.
We now extend the definition to general continuous functions. Suppose dg is a pseudo-metric on the space of bounded continuous functions (I-RR, ;R), We call f E (*[[-R, ; R) to be (1/M, M, S) hicrarchical for every e > O, there exists a (1/M, M) hierarchical (H, A) polyymomll fe such that: df fe) < E. We note some examples below:
1. Let y be the uniform measure over (-1, --,11 1)",""""" ds be the I,2 norm induced by jr. H = {1, and A be identity mapping. We note that functions over the unbiased Boolean hypercube satisfying the [1/M, MM ---tairce property in Definition I.1 correspond to (1/M, M, (²))))
hierarchical functions as defined above.
2. In the case when μ is the biased product measure over {-1.1}", we can take H {1, and A(x) = x Ex. This recovers the definition Section 3.1
3. When μ is the isotropic Gaussian measure, we can take R 0o, H to be the set of 1-D Hermite polynomials and A to be the identity. In case μ N (m, Σ), we instead take
A= E- m).
4. When R < co and S is the L norn with respect to the Lebesgue measure, C(I-R, RJ";; we can take H = (exp(i xdke)
R k E }} and A = I. This allows us to interpret AH, polynomial approximations as Fourier series approximations.
5. When R < do and S is the uniform norm (or sup norm) over C(I-R, R)"; RR,, we can take } and A = I. Since any continuous function can be approximated by H = 11,,, _² ,.. polynomial, this presents a large class of functions of interest.
In items 1-4, we consider these specific function classes H in order to make (H, monomials orthonormal under I (2² We leave it as a direction of future work to extend our theoretical learning
results in Theorem 2.2 to such function classes.
3.3 Composable chains
Finally, we discuss distinct way to generalize the staircase property. One can relax the strict inclusion property of Definition I.I with single element removed, to more general notions of increasing chains. For instance, (S) + O, one may require that there exists an S' such that [S'| < [S] and |SAS'| O(1), and we conjecture that regular networks will still learn sparse polynomials with this structure. More generally, one may require that for any S such that g(S) o O, there exists constant number of S,'s such that |Syl < |S| and O(S)) 7 0 for all and such that S can be composed by } and the input features æ1,.... , Tn, where in the Boolean setting the composition rule corresponds products. Finally, one could further generalize the results by changing the feature space, i.c., using regular networks that take not just the standard inputs TI,..., but also have other choices of features di (I"))..., 6p(x") as inputs, for p polynomial in n.
4 Limitations and societal impacts
For simplicity of the proofs, the architecture and training algorithm are not common in practice: quadratic activations, a sparse connectivity graph, and layer-wise training [39--]| with stochastic block coordinate descent. We also perturb the weights with noise in order to avoid saddle points [2]] and we prune the low-m wwwaannit weights to simplify the analysis (although this may not deteriorate performance much in practice (3] We emphasize that these limitations are purely technical as they make the analysis tractable, and we conjecture from our experiments that ReLU ResNets trained with SGD efficiently learn functions satisfying the staircase property. This work does not deal directly with real world data, so may not have direct societal impacts. However, it aims to rigorously understand and interpret deep learning, which may aid us in preventing unfair behavior by Al.
10

---

Acknowledgments
We are grateful to Philippe Rigollet for insightful conversations. EA was supported in part by the NSF-Simons Sponsored Collaboration on the Theoretical Foundations Deep Learning. NSF award 2031883 and Simons Foundation award 814639. EB was supported in part by an NSF Graduate Fellowship and an Apple Fellowship and NSF grant 202-4402448. GB was supported in part by NSF CAREER award CCF-1940205. DN supported in part by NSF grant DMS-
References
[1] Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom in; An introduction to circuits. Distill, 5(3)e00024-001,, 2020.
[2] Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks, In European conference on computer vision, pages 818-833. Springer. 2014.
[3] Emmanuel Abbe and Colin Sandon. On the universality of deep learning. In
H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20061-20072. Curran As- sociates, Inc., 2020. URL https://procesddigg neurips wwt.rrppp.cpppppa/aaeea cc/papprr2020//iie. htt.5/af9222222ccaaaaeee66661..2
[4] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus pac and sq learning. Preprint., 2021.
[5] Michael Kearns. Efficient noise-tolcrant learning from statistical queries. Journal of the ACM (JACM), 4566))983-1006, 1998.
[6] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 253-262, 1994.
[7] Shai Shalev-Shwartz. Ohad Shamir, and Shaked Shammah. Failures of gradient-basee deep learning. In International Conference on Machine Learning, pages 3067-3075. PMLR, 2017.
[8] Tejas Kulkarni. Karthik Narasimhan, Ardavan Sacedi, and Josh Tenenbaum. Hicrarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In NIPS, 2016.
[9] Heather Woltman, Andrea Feldstain, J Christine MacKay, and Meredith Rocchi. An introduction hierarchical linear modeling. Tutorials in quantitative methods for psychology, 8(1):52-69 2012.
[10] Nir Friedman, Dan Geiger, and Moises Goldszmidt. Bayesian network classifiers. Machine learning, 29(2): 1997.
[11] Lior Rokach and Oded Maimon. Clustering methods. In Data mining and knowledge discovery handbook, pages 321-352 Springer, 2005.
[12] Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE transactions on pattern analysis and machine intelligence, 1872))1872-188888 2013.
[13] Jong Chul Ye, Yoscob Han, and Eunju Cha. Deep convolutional framelets: A general deep learning framework for inverse problems. SIAM Journal on Imaging Sciences, 11(2)9911-1048, 2018.
[14] Ankit B Patel, Tan Nguyen, and Richard G Baraniuk. A probabilistic theory deep learning. arXiv preprint 150.00114
[15] Eran Malach and Shai Shalev-Shwartz. provably correct algorithm for deep learning that actually works. arXiv preprint arXiv:1803.09222 2018.

---

[16] Elchanan Mossel. Deep learning and hierarchal generative models. arXiv:1612.09057, 2016.
arXiv preprint
[17] Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. arXiv preprint
2019.
[18] Eran Malach and Shai Shalev-Shwartz. The implications of local correlation on learning some deep functions. Advances in Neural Information Processing Systems, 33, 2020.
[19] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. Learning functions: when is deep better than shallow. arXiv preprint wetp:o:0000000 2016.
[20] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
[21] Eran Malach and Shai Chalev-Shwartz Is deeper better only when shallow is good? arXiv preprint arXiv: 03488, 2019.
[22] Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pages 1517-1539. PMLR, 2016.
[23] Guy Bresler and Dheeraj Nagaraj. Sharp representation theorems for relu networks with precise dependence on depth. Advances in Neural Information Processing Systems, 33, 2020.
[24] Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. arXiv preprint arXiv:2006. 20t.::20006.33366, 2020.
[25] Zeyuan Allen-Zhi and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv: 10337,0311
[26] Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning, arXiv preprint arXiv:2001.00 044441000..4411,, 2020.
[27] Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv: 1312.6120, 2013.
[28] Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In Advances Neural Information Processing Systems, volume 32, 2019, URL
nwurips. /ouripps.cc/ppppet2//////eee
Paper pdf
[29] Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint arXiv: 1909, /205 2019.
[30] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin L Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. {SGD) on neural networks learns functions of increasing complex- ity. In Advances in Neural Information P Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019.
[31] Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint Stti::2000.143999 2020.
[32] Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks gen- eralize better than deep feedforward networks? neural tangent kernel perspective. Advances in Neural Information Processing Systems, 33, 2020.
[33] Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning polynomials with neural networks. In International conference on machine learning, pages 1908-1916. PMLR, 2014.
[34] Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for under- standing neural networks. arXiv preprint 1rX1v:1904.00687, 2019.
12

---

[35] Guy Bresler and Dheeraj Nagaraj. A corrective view of neural networks: Representation. memorization and learning. In Conference on Learning Theory, pages 848-901. PMLR, 2020.
[36] Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. arXiv preprint arXiv:2103.012100 2021.
[37] Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 395-404. IEEE, 2009.
[38] Alon Brutzkus, Amit Daniely, and Eran Malach. 1d3 learns juntas for smoothed product distributions. In Conference on Learning Theory, pages 902-915. PMLR, 2020.
[39] Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. International conference on machine learning, pages 583-593, PMLR, 2019.
[40] Arild Nøkland and Lars Hiller Eidnes. Training neural networks with local error signals. In International Conference Machine Learning, pages 4839-4850. PMLR, 2019.
[41] Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Decoupled greedy learning of cnns. In International Conference on Machine Learning, pages 736-745. PMLR, 2020.
[42] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
[43] Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights and connections for efficient neural networks. arXiv preprint arXiv:1506.0262). 2015.
[44] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Defini-
tion I. and Theorem 2.2
(b) Did you include complete proofs of all theoretical results? [Yes] See supplemental material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen- tal material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Supplemental material
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A] Do not experiment multiple times.
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See supplemental material.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 'r using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "kMPWiVSlRzv", "reviewer": "Reviewer_n6Y2", "summary": "The paper discussed the learnability of function by neural networks.\n\nThe 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.\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "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.\n\nThe 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). \n\nThe 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.\n\nOverall I consider the findings of this paper interesting although not groundbreaking.\n\nEDIT:\n\nI'm satisfied with the authors response, I've increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I'd like more discussion of how the paper claims reconcile with the observed non-hierarchical behavior.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ESmmhUG7el0", "reviewer": "Reviewer_1A1u", "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "**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. \n\n## Overview\n\nThe 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.\n\nMy 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?\n\n## Limitations\n\nThe 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. \n\n## Clarity\n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed relevant limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ABeAP7txfg2", "reviewer": "Reviewer_JJ8b", "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.   ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "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. \n\nOne 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). \n\nHowever, 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. \n\nThere 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.\n\nOverall, 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.\n\n 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$. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "1OZhx9dQxJ", "reviewer": "Reviewer_dLyL", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Strength:\n\nThe 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. \n\nWeakness and comments:\n\nThe 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.\n\n[a] Lyu and Li, Gradient Descent Maximizes the Margin of Homogeneous Neural Networks.\n\nThe 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. \n\nThe 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.\n\nThe 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.\n\nBesides, 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.\n \nMinors:\n\nFor the equation above line 165, y is not defined. I guess that it shall be defined by y=Ax+b. \n\nIn 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}$. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)