The staircase property: How hierarchical structure can guide deep learning
Year: 2022

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.

heading: 1 Introduction
text: It has been observed empirically that neural networks can learn hierarchically. For example, a ‘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. [1, 2]). 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 regular1DNNs are able to learn them?
This is a 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 to capture naturally occurring data of interest, so the structural assumption must make conceptual sense. (2) Interpretability: If we hope to clearly interpret the inner workings of neural networks, understanding both how they classify and also how they learn, then we need a model for data that is interpretable to
1The notion of regularity is specified in Definition 2.1; this means network architectures and initializations that have homogeneity properties within layers, in contrast to the emulation architectures in [3, 4].
35th Conference on Neural Information Processing Systems (NeurIPS 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 a sense defined later on. This prevents using carefully-crafted architectures and initializations to emulate general learning algorithms [3, 4]. 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 1.1.
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 : {+1, 1}n ! R can be decomposed in the Fourier-Walsh basis as
f(x) = X
S✓[n]
f̂(S) S(x), where f̂(S) := hf, Si, S(x) := Y
i2S xi (1)
and the inner product between two functions is hf, gi = Ef(X)g(X) for X ⇠ Unif({+1, 1}n). This decomposition expresses f(x) as a sum of components, each of which is a monomial S(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  n/2 (i.e., the class { S}S✓[n],|S|=k) is efficiently learnable by Statistical Query (SQ) algorithms if and only if k is constant [5, 6], and the same holds for noisy Gradient Descent (GD) on neural nets with polynomially-many parameters [5], and for noisy Stochastic Gradient Descent (SGD) where the batch-size is sufficiently large compared to the gradients’ precision [3, 4]. This was also noted in [7] which shows that gradients carry little information to reconstruct S for large |S|, and hence gradient-based training is expected to fail. Thus, we can think of a component S 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 function (and its orbit class induced by permutations of the inputs), which is a sum of monomials of increasing degree:
Sk(x) = x1 + x1x2 + x1x2x3 + x1x2x3x4 + · · ·+ 1:k . (2)
Here Sk(x) has a hierarchical structure, where x1 builds up to x1x2, which builds up to x1x2x3, and so on until the degree-k monomial 1:k. Our experiments in Fig. 2 show a dramatic difference between learning a single monomial 1:k and learning the staircase function Sk. Even with n = 30 and k = 10, the same network with 5 ReLU ResNet layers and the same hyperparameters can easily learn Sk to a vanishing error (Fig. 2b) whereas, as expected, it cannot learn 1:k even up to any non-trivial error since 1:k is a high-degree monomial (Fig. 2a).
An explanation for this phenomenon is that the neural network learns the staircase function Sk(x) by first learning a degree-1 approximation that picks up the feature x1, and then uses this to more readily learn a degree-2 approximation that picks up the feature x1x2, and so on, progressively incrementing the degree of the approximation and ‘climbing the staircase’ up to the large degrees. We refer to Fig. 1a for an illustration. This is indeed the learning mechanism, as we 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 1:10 cannot learn any Fourier coefficient relevant to 1: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 1:10 coefficient.
Main results We shed light on this phenomenon, proving that certain regular networks efficiently learn the staircase function Sk(x), and, more generally, functions satisfying this structural property: Definition 1.1 (Staircase property). For any M > 1, a function g : { 1, 1}n ! R satisfies the [1/M,M ]-staircase property over the unbiased binary hypercube if:
• for all S ⇢ [n], if ĝ(S) 6= 0 then |ĝ(S)| 2 [1/M,M ].
• for all S ⇢ [n], if ĝ(S) 6= 0 and |S| 2, there is S0 ⇢ S such that |S \ S0| = 1 and ĝ(S0) 6= 0.
Furthermore, g is said to be an s-sparse polynomial if |{S : ĝ(S) 6= 0}|  s.
The parameters M and s appear naturally since a PAC-learning algorithm for s-sparse polynomials satisfying the [1/M,M ]-staircase 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 of higher degree:
Theorem 1.2 (Informal statement of Theorem 2.2). Let g : { 1, 1}n ! R be an unknown s-sparse polynomial satisfying the [1/M,M ]-staircase property. Given access to random samples from {(x, g(x))}x⇠{ 1,1}n , there is a regular neural network architecture that approximately learns g in poly(n, s,M) time and samples when trained with layerwise stochastic coordinate descent.
Even though we only consider hierarchical functions over the Boolean hypercube { 1, 1}n in our theoretical result, we believe that the techniques used in this work can be extended to other function spaces of interest, exploiting the orthonormality of the corresponding Fourier basis functions. For this reason we give a fairly general definition of hierarchical functions in Section 3 that goes beyond the Boolean hypercube, as well as beyond the strict notion of increasing chains. This more general class of functions is of further interest because it includes as special cases well-studied classes such as biased sparse parities and decision trees in a smoothed complexity setting (see Section 3.1).

heading: 1.1 Related Work
text: Statistical query emulation results For the general class of polynomial-size neural network architectures with any choice of initialization, it is known that SGD on a sufficiently small batch-size can learn2 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 initializations, 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 [4] for “regular” architectures and initializations as defined in Definition 2.1. In contrast, our architecture in Theorem 2.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 a given algorithm.
Consider also the orbit class under permutations of the inputs of the “truncated staircase function”, Sj!k(x) = P k
i=j i:k(x), for 1  j  k  n. Note that this class is efficiently SQ-learnable when k = n, since the monomial 1:n is always present and one can recursively check which sub-monomial is present or not by checking at most n monomials at each step. However, we conjecture that Sj!n(x) is not learnable by regular networks trained with gradient descent if min(n j, j) = !(1). Therefore such truncated staircases provide a candidate for separating gradient-based learning on regular networks versus general, non-regular networks that allow for emulating any SQ algorithm [4].
Hierarchical models of data Explicitly adding hierarchical structures into machine learning algorithms such as hierarchical Bayesian modeling and hierarchical linear modeling has proved successful in various machine learning tasks beyond deep learning [8–11]. For image data, [12, 13] 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 a ‘deep rendering model’ which hierarchically models levels of abstraction present in data, but does not prove learnability. [15] gives a 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 [16] 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, [18], studies learning Boolean circuits of depth O(log n) via neural networks under product distributions using layer-wise gradient descent. While [18] 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 a class of compositionally-created functions more efficiently than shallow networks. [20] shows that certain smooth radial functions can be easily represented by three-layer networks but need exponentially-many neurons to be represented by a two-layer network. Based on an analysis of learning fractal distributions related to the Cantor set, [21] conjectures that if shallow networks are poorly represent a target function, then a 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 on 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 a twohidden-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-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 a teacher network that is well-conditioned, has quadratic activations and has a 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 our work (e.g., we can learn polynomials up to degree n,
2These reductions are for polynomial-time algorithms and for polynomial precisions on the gradients.
whereas [26] 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 [27–29], gradient dynamics are explored for the simplified case of deep linear networks, where an ‘incremental learning’ phenomenon is observed in which the singular values are learned sequentially, one after the other. This phenomenon is reminiscent of the incremental learning of the Fourier coefficients of the Boolean function in our setting (Fig. 2). For real world data sets, [30] 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.
Neural Tangent Kernel and random features A sequence of papers have studied convergence 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 kernel methods and give training and/or generalization guarantees. Because of the reduction to kernels, these results are essentially non-hierarchical. [31, 32] in fact show that deep networks in the NTK regime behave no 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–35] which consider learning low-degree (degree q) polynomials over Rn, without a hierarchical structure assumption. They require n⌦(q) neurons to learn such functions, which is super-polynomial once q 1. The results hold in the random features regime, known to be weaker than NTK.

heading: 1.2 Organization
text: In Section 2, 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 3 we discuss possible extensions, defining hierarchical functions satisfying the staircase property in a greater level of generality from Definition 1.1. We refer to Appendix A for additional experiments which validate our theory and conjectures for both the simplest definition of the staircase property in Definition 1.1 and the generalizations in Section 3.2.

heading: 2 Regular networks provably learn hierarchical Boolean functions
text: We state our main theoretical result, which proves that a regular neural network trained with a descent algorithm learns hierarchical Boolean functions in polynomial time.

heading: 2.1 Architecture
text: Our network architecture has neuron set V and edge set E, and is defined as follows (see also Fig. 1b). The neuron set is V = Vin t V1 t . . . VL. Here Vin = {vin,0, vin,1, . . . , vin,n} is a set of n+1 inputs, and each intermediate layer consists of |Vi| = W neurons. Furthermore, the edge set E is a sparse, random subset of all possible directed edges:
• each (v0, vi) 2 Vin ⇥ Vi is in the edge set E independently with probability p1, and • each (vi, vi+1) 2 Vi ⇥ Vi+1 for i 2 [L 1] is in the edge set E independently with
probability p2.
For each edge e 2 E, let there be a weight parameter ae 2 R. And for each neuron v 2 V \ Vin, let there be a bias parameter bv 2 R. The parameters of the network are therefore a 2 RE and b 2 RV \Vin . For simplicity of notation, we concatenate these two vectors into one vector of parameters
w = [a b] 2 RE RV \Vin . For each i 2 [n], the ith input, vin,i 2 Vin, computes xi, and the 0th input, vin,0, computes a constant:
fvin,i(x;w) = xi, and fvin,0(x;w) = 1. Given a neuron v 2 V \ Vin, the function computed at that neuron is a quadratic function of a linear combination of neurons with edges to v, (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:
fv(x;w) =
0 @ X
e=(u,v)2E
aefu(x;w)
1 A 2
+ bv, and f(x;w) = X
v2V \Vin
fv(x;w).
Our architecture satisfies the following regularity condition: Definition 2.1 (Regular network architecture and initialization). An architecture is regular if for any 1  i  j  L, for any distinct pair of potential edges (vi, vj), (v0i, v0j) 2 Vi ⇥ Vj , the events that these edges are in E are i.i.d.; the same holds for any distinct pair of potential edges (u, vj), (u0, v0j) 2 Vin ⇥ Vj; the same holds for any distinct pair of potential edges (u, vout), (u0, vout) 2 Vj ⇥ vout (where vout is the output vertex). Furthermore, the initialization is regular if it is i.i.d. over the set of present edges and each weight has a symmetric distribution.
In our case the weight initialization is i.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.

heading: 2.2 Loss function
text: Let the loss function be the mean-squared-error between the output f of the network and a function g : { 1, 1}n ! R that we wish to learn. Namely, for any x 2 { 1, 1}n, a 2 RE and b 2 RV \Vin , define the point-wise loss and population loss functions respectively, where w = [a, b]:
`(x;w) = 1
2 (f(x;w) g(x))2; `(w) = Ex⇠{ 1,1}n`(x;w) . (3)
We will train the neural network parameters to minimize an L2-regularized version of the loss function. Let 1, 2 > 0 be regularization parameters, and define the point-wise regularized loss `R(x;w) = `(x;w) +R(w) and the population regularized loss `R(w) = `(w) +R(w), where
R(w) = 1
2
X
e=(u,v)2E u2Vin
1a 2 e +
1
2
X
e=(u,v)2E u 62Vin
2a 2 e .
The distinct regularization parameters 1, 2 > 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.

heading: 2.3 Training
text: We train the neural network to learn a function g : { 1, 1}n ! R by running Algorithm 1. This algorithm trains layer-wise from layer 1 to layer L. The ith layer is trained with stochastic block coordinate descent, iterating through the neurons in Vi in an arbitrary fixed order, and training the parameters of each neuron v 2 Vi using the TRAINNEURON subroutine. Each call of TRAINNEURON runs stochastic gradient descent to train the subset of neural network parameters wv = {ae}e=(u,v)2E [ {bv} directly associated with neuron v (i.e., the weights of the edges that go into v, and the bias of v), keeping the other parameters w v = {ae}e=(u0,v0)2E s.t. v 6=v0 [ {bv0}v02V \({v}[Vin) fixed.
Algorithm 1: TRAINNETWORKLAYERWISE Input: Sample access to the distribution {(x, g(x))}x⇠{ 1,1}n . Hyperparameters W,L, p1, p2, 1, 2, ⌘, B, ✏stop,↵, ⌧ . Output: Trained parameters of neural network after training layer-wise.
1 (V,E) random network constructed as in Section 2.1. 2 w0 ~0, t 0 // Initialize all weights and biases to zero. 3 for layer i = 1 to L do 4 for neuron v 2 Vi do // Train the neuron parameters, wv, fixing other parameters 5 wt+1 TRAINNEURON(v, wt; 1, 2, ⌘, B, ✏stop,↵, ⌧) 6 t t+ 1 7 end 8 end 9 Return wt
Algorithm 2: TRAINNEURON(v, w0; 1, 2, ⌘, B, ✏stop,↵, ⌧) Input: Neuron v 2 V \ Vin. Initial network parameters w0. Access to random samples (x, g(x)) for x ⇠ { 1, 1}n. Hyperparameters 1, 2, ⌘, B, ✏stop,↵, ⌧ . Output: Parameters of network after the subset of parameters wv of neuron v is perturbed and then trained with NEURONSGD, while all other parameters w v remain fixed. // To avoid saddle points, randomly perturb the neuron parameters
1 wperturb v
w 0 v + z, where z is a noise vector whose entries are i.i.d. in Unif([ ⌘, ⌘]).
2 wperturb [w0 v, w perturb v ]
// Run stochastic gradient descent on neuron parameters, until approximate stationarity
3 wSGD NEURONSGD(v, wperturb; 1, 2, B, ✏stop,↵)
// Prune the neuron’s small weights 4 wround
v w SGD v , rounding to 0 every entry of magnitude less than ⌧ 5 Return wround = [w0 v, wroundv ]
Algorithm 3: NEURONSGD(v, w0; 1, 2, ⌘, B, ✏stop,↵, ⌧) Input: Neuron v 2 V \ Vin. Initial network parameters w0. Access to random samples (x, g(x)) for x ⇠ { 1, 1}n. Hyperparameters 1, 2, ⌘, B, ✏stop,↵, ⌧ . Output: Parameters of network after the subset of parameters wv corresponding to neuron v is
trained, all other parameters w v remain fixed. 1 t 0 2 while true do // Approximate rwv`R with minibatch size B 3 Draw i.i.d. data samples (xt,1, g(xt,1)), . . . , (xt,B , g(xt,B)) 4 ⇠t 1
B
P B
i=1rwv`R(x t,i;w0 v, w t v )
// Stop if we have reached an approximate stationary point 5 if k⇠tk  ✏stop then break out of the loop; // Update wv in direction of the approximate gradient 6 wt+1
v w t v ↵⇠ t
7 t t+ 1
8 Return [w0 v, wtv]

heading: 2.4 Theoretical result
text: We prove that Algorithm 1 learns functions satisfying the staircase property in the sense of Definition 1.1. We defer the exact bounds on the parameters considered to Appendix B. Theorem 2.2. Let g : { 1, 1}n ! R be an unknown s-sparse polynomial satisfying the [1/M,M ]- staircase property for some given s,M > 1. Given an accuracy parameter ✏ > 0, a soundness parameter 0 < < 1, and access to random samples from {(x, g(x))}x⇠{ 1,1}n , there is a setting of hyperparameters for Algorithm 1 that is polynomially-bounded, i.e.,
1/ poly(n, s,M, 1/✏, 1/ ) W,L, p1, p2, 1, 2, ⌘, B, ✏stop,↵, ⌧  poly(n, s,M, 1/✏, 1/ ),
such that Algorithm 1 runs in poly(n, s,M, 1/✏, 1/ ) time and samples and with probability 1 returns trained weights w satisfying the bound `(w)  ✏ on the population loss.

heading: 2.5 Proof overview
text: We now briefly describe how Algorithm 1 learns, giving a high-level depiction of the training process in the case that the target function is the staircase function S3(x) = x1 + x1x2 + x1x2x3. We refer to Fig. 3 for an 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 a non-zero function). Initially all neurons are blank and the total output of the network is 0.
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 is because we can bound the number of active neurons at any iteration during training by s + n + 1, so the number of neuron tuples (u1, u2, u3, v) 2 V 4 such that u1, u2, u3 are active and all have edges to v is in expectation bounded by (s+ n+ 1)3(p1)3W ⌧ 1. Since any neuron during training has at most two active parents, we may tractably analyze TRAINNEURON for training new neurons: in a key technical lemma, we show that every active neuron v has exactly two active parents u and u0, and approximately computes a monomial given by the product of the parents’ values, fv(x) ⇡ Sv ⇡ fu(x)fu0(x).
We cannot set p1 and p2 to be too small or else the network will not be connected enough to learn. Thus, we must also set the connectivity parameters so that for any pair (u, u0) 2 Vin ⇥ (V \ VL), the neurons u and u0 share many children, and at least one of these children may learn the product if it is useful. For this it is sufficient to take the expected number of shared children p1p2W 1 very large. We now present a run of the algorithm, breaking it up into “steps” for exposition.
Step 1: 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, x2 = x2 · 1. But the mean-squared error cannot decrease by learning x2, since x2 is orthogonal to the staircase function in the L2 sense (i.e., hS3(x), x2i = 0, because the staircase function does not have x2 as a monomial), so the neuron v remains blank. Let t1 be the first iteration at which the algorithm reaches a neuron n1 2 V1 that has x1 and 1 as inputs. When the network trains n1 using the sub-routine, we show that it learns to output x1 = x1 · 1, since that is the highest-correlated function to S3(x) that n1 can output. Combined with the linear layer, the overall neural network output becomes f(x;wt1) ⇡ x1.
Step 2: The error function after Step 1 is E1(x) = S3(x) f(x;wt1) ⇡ x1x2 + x1x2x3. Again, for many iterations the training procedure keeps neurons blank, until at iteration t2 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 x1x2, which is the function with highest correlation to E1(x) which n2 can output. Thus, the neural network now learns to output f(x;wt2) ⇡ x1 + x1x2, so the error function has decreased to E2(x) = S3(x) f(x;wt2) ⇡ x1x2x3. The training proceeds in this manner until all the monomials in S3(x) are learned by the network.
Error Propagation and Regularization: A significant obstacle in analyzing layer-wise training is 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 1, 2 and connectivity parameters p1, p2 for edges from inputs versus edges from neurons. In our proof of Theorem 2.2, we set 1 ⌧ 2 and p1 p2, which ensures that after training a neuron (say n2 above) the weight from the neuron n1 (which has regularization parameter 2) is much smaller than the weight directly from the input x2 (which has regularization parameter 1). Since the inputs are noise-free, this disallows exponential growth of errors along the 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 1 = 2 and p1 = p2, because of a backward feature correction phenomenon [26] where the lower layers’ accuracy improves as higher levels are trained.

heading: 3 General Hierarchical Structure

heading: 3.1 Extension to biased binary inputs and implications
text: We extend the main result of this paper to more general setting of functions over a space of i.i.d. binary variables that have zero expectation but are not necessarily supported on {+1, 1}. For instance, if {Xi}i2[n] are i.i.d. and Boolean (on {+1, 1}) with E(Xi) = b for some b 2 [ 1, 1], the centered variables X̃i = Xi b are valued in {1 b, 1 b}. Over these centered variables, the Fourier coefficients of a function are given (up to normalization) by f̂(S) = E
X̃ f(X̃) Q i2S X̃i
for any S ⇢ [n]. Thus, the staircase property of Definition 1.1 generalizes clearly: the function f : {1 b, 1 b}n ! R satisfies the staircase property if for any S ⇢ [n] with |S| 2 such that f̂(S) 6= 0, there is a subset S0 ⇢ S such that |S \ S0| = 1 and f̂(S0) 6= 0.
Showing a similar result to Theorem 2.2 for staircase functions on the variables X̃i with a quadratic activation requires a slight modification of our argument since X̃2
i is no longer constant (and equal
to 1), so one cannot use the simple identity Z1Z2 = (Z1 + Z2)2/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 r1r2 = ((r1+ r2)2 r21 r 2 2)/2, one can hierarchically learn new features as products of previouslylearned features. Alternatively, one can change the activation so that each neuron maps a vector input v to (a · v + b)2 + c · y.2, where a, b, c are trainable parameters, to learn products of general binary variables. A 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 a {+1, 1}-valued input distribution that is i.i.d. with EX1 = 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 is 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 a regular network as considered in this paper. However, sparse biased parities are staircase functions over unbiased binary variables, with polynomially-many nonzero coefficients since the degree is 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 log(n)-depth decision trees satisfies the general staircase property. This is because Lemma 3 in [37] implies that with high probability there is a poly(n/✏)-sparse polynomial that ✏-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.3

heading: 3.2 Extension to more general L2 spaces
text: We now give an even more general version of the staircase property in Definition 1.1. Since neural networks are efficient at representing affine transforms of the data and smooth low-dimensional functions [35], we generalize the class of hierarchical functions over the space of continuous, real valued functions [ R,R]n ✓ Rn;R 2 R+ [ {1} without any reference to underlying measures but with enough flexibility to add additional structures like measures and the corresponding L2 norms. Set R 2 R+ [ {1} and consider any sequence of functions H := {hk : R! R}k2N[{0} such that h0 is the constant function 1, and any affine transform A : Rn ! Rn such that A(x) = Ax+ b for A 2 Rn⇥n; b 2 Rn. We call a function f : [ R,R]d ! R to be (H,A)-polynomial if there exists a finite index set If ⇢ (N [ {0})n such that for some real numbers (↵k)k2If :
f(x) = P k:=(k1,...,kn)2If ↵k Q n i=1 hki(yi)
3Such a conjecture was recently made by [38], which leaves as an open problem in Section 1.3 whether neural networks can learn log(n)-juntas in a smoothed complexity setting, and implicitly poses the same problem about the more general case of log(n)-depth decision trees.
Where y := A(x). We also define Ord(k) := |{i : ki 6= 0}| and a partial order ‘ ’ over (N [ {0})n such that k0 k iff k0
i 2 {0, ki} for every i 2 [n]. For M 1, we will call a (H,A)-polynomial to
be (1/M,M) hierarchical if
1. 1/M  |↵k| M for every k 2 If . 2. For every k 2 If such that Ord(k) 2, there exists k0 2 If such that Ord(k0) = Ord(k) 1
and k0 k.
We now extend the definition to general continuous functions. Suppose dS is a pseudo-metric on the space of bounded continuous functions Cb([ R,R]n;R). We call f 2 Cb([ R,R]n;R) to be (1/M,M,S) hierarchical if for every ✏ > 0, there exists a (1/M,M) hierarchical (H,A)-polynomial f✏ such that: dS(f, f✏) < ✏. We note some examples below:
1. Let µ be the uniform measure over { 1, 1}n, dS be the L2 norm induced by µ, H = {1, x} and A be identity mapping. We note that functions over the unbiased Boolean hypercube satisfying the [1/M,M ]-staircase property in Definition 1.1 correspond to (1/M,M,L2(µ)) hierarchical functions as defined above.
2. In the case when µ is the biased product measure over { 1, 1}n, we can take H = {1, x} and A(x) = x Ex. This recovers the definition in Section 3.1.
3. When µ is the isotropic Gaussian measure, we can take R = 1, H to be the set of 1-D Hermite polynomials and A to be the identity. In case µ = N (m,⌃), we instead take A = ⌃ 1/2(x m).
4. When R <1 and S is the L2 norm with respect to the Lebesgue measure. C([ R,R]n;R), we can take H = {exp(i⇡kx
R ) : k 2 Z} and A = I . This allows us to interpret (H,A)-
polynomial approximations as Fourier series approximations. 5. When R <1 and S is the uniform norm (or sup norm) over C([ R,R]n;R), we can take
H = {1, x, x2, . . . , } and A = I . Since any continuous function can be approximated by a 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,A) monomials orthonormal under L2(µ). We leave it as a direction of future work to extend our theoretical learning results in Theorem 2.2 to such function classes.

heading: 3.3 Composable chains
text: Finally, we discuss a distinct way to generalize the staircase property. One can relax the strict inclusion property of Definition 1.1 with a single element removed, to more general notions of increasing chains. For instance, if ĝ(S) 6= 0, one may require that there exists an S0 such that |S0| < |S| and |S S0| = 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) 6= 0, there exists a constant number of Sj’s such that |Sj | < |S| and ĝ(Sj) 6= 0 for all j, and such that S can be composed by {Sj} and the input features x1, . . . , xn, where in the Boolean setting the composition rule corresponds to products. Finally, one could further generalize the results by changing the feature space, i.e., using regular networks that take not just the standard inputs x1, . . . , xn, but also have other choices of features 1(xn), . . . , p(xn) as inputs, for p polynomial in n.

heading: 4 Limitations and societal impacts
text: 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–41] with stochastic block coordinate descent. We also perturb the weights with noise in order to avoid saddle points [42], and we prune the low-magnitude weights to simplify the analysis (although this may not deteriorate performance much in practice [43]). 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 AI.

heading: Acknowledgments
text: We are grateful to Philippe Rigollet for insightful conversations. EA was supported in part by the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of 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 DMS-2022448. GB was supported in part by NSF CAREER award CCF-1940205. DN was supported in part by NSF grant DMS-2022448.

Review summaries:
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. 

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.

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.